{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minesweeper"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: updateBoard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扫雷游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>让我们一起来玩扫雷游戏！</p>\n",
    "\n",
    "<p>给你一个大小为 <code>m x n</code> 二维字符矩阵&nbsp;<code>board</code> ，表示扫雷游戏的盘面，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'M'</code>&nbsp;代表一个 <strong>未挖出的</strong> 地雷，</li>\n",
    "\t<li><code>'E'</code>&nbsp;代表一个<strong> 未挖出的 </strong>空方块，</li>\n",
    "\t<li><code>'B'</code><strong>&nbsp;</strong>代表没有相邻（上，下，左，右，和所有4个对角线）地雷的<strong> 已挖出的 </strong>空白方块，</li>\n",
    "\t<li><strong>数字</strong>（<code>'1'</code> 到 <code>'8'</code>）表示有多少地雷与这块<strong> 已挖出的</strong> 方块相邻，</li>\n",
    "\t<li><code>'X'</code>&nbsp;则表示一个<strong> 已挖出的</strong> 地雷。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数数组 <code>click</code> ，其中 <code>click = [click<sub>r</sub>, click<sub>c</sub>]</code> 表示在所有<strong> 未挖出的 </strong>方块（<code>'M'</code> 或者 <code>'E'</code>）中的下一个点击位置（<code>click<sub>r</sub></code> 是行下标，<code>click<sub>c</sub></code> 是列下标）。</p>\n",
    "\n",
    "<p>根据以下规则，返回相应位置被点击后对应的盘面：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>如果一个地雷（<code>'M'</code>）被挖出，游戏就结束了- 把它改为&nbsp;<code>'X'</code> 。</li>\n",
    "\t<li>如果一个<strong> 没有相邻地雷 </strong>的空方块（<code>'E'</code>）被挖出，修改它为（<code>'B'</code>），并且所有和其相邻的<strong> 未挖出 </strong>方块都应该被递归地揭露。</li>\n",
    "\t<li>如果一个<strong> 至少与一个地雷相邻</strong> 的空方块（<code>'E'</code>）被挖出，修改它为数字（<code>'1'</code> 到 <code>'8'</code> ），表示相邻地雷的数量。</li>\n",
    "\t<li>如果在此次点击中，若无更多方块可被揭露，则返回盘面。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2023/08/09/untitled.jpeg\" style=\"width: 500px; max-width: 400px; height: 269px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"E\",\"E\",\"E\",\"E\",\"E\"],[\"E\",\"E\",\"M\",\"E\",\"E\"],[\"E\",\"E\",\"E\",\"E\",\"E\"],[\"E\",\"E\",\"E\",\"E\",\"E\"]], click = [3,0]\n",
    "<strong>输出：</strong>[[\"B\",\"1\",\"E\",\"1\",\"B\"],[\"B\",\"1\",\"M\",\"1\",\"B\"],[\"B\",\"1\",\"1\",\"1\",\"B\"],[\"B\",\"B\",\"B\",\"B\",\"B\"]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2023/08/09/untitled-2.jpeg\" style=\"width: 500px; max-width: 400px; height: 275px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"B\",\"1\",\"E\",\"1\",\"B\"],[\"B\",\"1\",\"M\",\"1\",\"B\"],[\"B\",\"1\",\"1\",\"1\",\"B\"],[\"B\",\"B\",\"B\",\"B\",\"B\"]], click = [1,2]\n",
    "<strong>输出：</strong>[[\"B\",\"1\",\"E\",\"1\",\"B\"],[\"B\",\"1\",\"X\",\"1\",\"B\"],[\"B\",\"1\",\"1\",\"1\",\"B\"],[\"B\",\"B\",\"B\",\"B\",\"B\"]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>board[i][j]</code> 为 <code>'M'</code>、<code>'E'</code>、<code>'B'</code> 或数字 <code>'1'</code> 到 <code>'8'</code> 中的一个</li>\n",
    "\t<li><code>click.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= click<sub>r</sub> &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= click<sub>c</sub> &lt; n</code></li>\n",
    "\t<li><code>board[click<sub>r</sub>][click<sub>c</sub>]</code> 为 <code>'M'</code> 或 <code>'E'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minesweeper](https://leetcode.cn/problems/minesweeper/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minesweeper](https://leetcode.cn/problems/minesweeper/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"E\",\"E\",\"E\",\"E\",\"E\"],[\"E\",\"E\",\"M\",\"E\",\"E\"],[\"E\",\"E\",\"E\",\"E\",\"E\"],[\"E\",\"E\",\"E\",\"E\",\"E\"]]\\n[3,0]', '[[\"B\",\"1\",\"E\",\"1\",\"B\"],[\"B\",\"1\",\"M\",\"1\",\"B\"],[\"B\",\"1\",\"1\",\"1\",\"B\"],[\"B\",\"B\",\"B\",\"B\",\"B\"]]\\n[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        q = deque()\n",
    "        x,y = click\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return board\n",
    "        q.append((x,y))\n",
    "        m,n = len(board),len(board[0])\n",
    "        drt = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]\n",
    "        def cal(i, j):\n",
    "            res = 0\n",
    "            for x in [1, -1, 0]:\n",
    "                for y in [1, -1, 0]:\n",
    "                    if x == 0 and y == 0: continue\n",
    "                    if 0 <= i + x < m and 0 <= j + y < n and board[i + x][j + y] == \"M\": res += 1\n",
    "            return res\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            count = cal(x,y)\n",
    "            if count:\n",
    "                board[x][y] = str(count)\n",
    "                continue\n",
    "\n",
    "            board[x][y]='B'\n",
    "            for dx,dy in drt:\n",
    "                x1,y1 = dx+x,dy+y\n",
    "                if  0<=x1<m and 0<=y1<n and board[x1][y1] == 'E':\n",
    "                    q.append((x1,y1))\n",
    "                    board[x1][y1] = 'B'\n",
    "        return board\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        q = deque()\n",
    "        x,y = click\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return board\n",
    "        q.append((x,y))\n",
    "        m,n = len(board),len(board[0])\n",
    "        drt = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]\n",
    "        def cal(i, j):\n",
    "            res = 0\n",
    "            for x in [1, -1, 0]:\n",
    "                for y in [1, -1, 0]:\n",
    "                    if x == 0 and y == 0: continue\n",
    "                    if 0 <= i + x < m and 0 <= j + y < n and board[i + x][j + y] == \"M\": res += 1\n",
    "            return res\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            count = cal(x,y)\n",
    "            if count:\n",
    "                board[x][y] = str(count)\n",
    "                continue\n",
    "\n",
    "            board[x][y]='B'\n",
    "            for dx,dy in drt:\n",
    "                x1,y1 = dx+x,dy+y\n",
    "                if  0<=x1<m and 0<=y1<n and board[x1][y1] == 'E':\n",
    "                    q.append((x1,y1))\n",
    "                    board[x1][y1] = 'B'\n",
    "        return board\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def BFS(start):\n",
    "            queue = collections.deque()\n",
    "            queue.append(start)\n",
    "            while queue:\n",
    "                nx, ny = queue.popleft()\n",
    "                count = 0\n",
    "\n",
    "                for x, y in [(nx+1, ny), (nx-1, ny),(nx, ny+1),(nx, ny-1),\\\n",
    "                    (nx+1, ny+1),(nx+1, ny-1),(nx-1, ny-1),(nx-1, ny+1)]:\n",
    "                    if 0 <= x < len(board) and 0 <= y < len(board[0]) \\\n",
    "                        and board[x][y] == \"M\":\n",
    "                        count += 1\n",
    "                if count == 0:\n",
    "                    board[nx][ny] = \"B\"\n",
    "                    for x, y in [(nx+1, ny), (nx-1, ny),(nx, ny+1),(nx, ny-1),\\\n",
    "                    (nx+1, ny+1),(nx+1, ny-1),(nx-1, ny-1),(nx-1, ny+1)]:\n",
    "                        if 0 <= x < len(board) and 0 <= y < len(board[0]) \\\n",
    "                            and board[x][y] == \"E\" :\n",
    "                            board[x][y] = \"B\" \n",
    "                            queue.append((x, y))\n",
    "                else:\n",
    "                    board[nx][ny] = str(count)\n",
    "            return board\n",
    "\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "        return BFS(tuple(click))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        x, y = click[0], click[1]\n",
    "        if board[x][y] == \"M\":\n",
    "            board[x][y] = \"X\"\n",
    "            return board\n",
    "        elif board[x][y] != \"E\":\n",
    "            return board\n",
    "        \n",
    "        def countM(x, y):\n",
    "            count = 0\n",
    "            min_x = max(0, x-1)\n",
    "            max_x = min(x+2, m)\n",
    "            min_y = max(0, y-1)\n",
    "            max_y = min(y+2, n)\n",
    "            for i in range(min_x, max_x):\n",
    "                for j in range(min_y, max_y):\n",
    "                    if board[i][j] == \"M\":\n",
    "                        count += 1\n",
    "            return count\n",
    "\n",
    "        que = collections.deque()\n",
    "        que.append((x, y))\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            if 0 <= x < m and 0 <= y < n and board[x][y] == \"E\":\n",
    "                count = countM(x, y)\n",
    "                # print(count)\n",
    "                if count != 0:\n",
    "                    board[x][y] = str(count)\n",
    "                    continue\n",
    "                board[x][y] = \"B\"\n",
    "                que.append((x-1, y))\n",
    "                que.append((x+1, y))\n",
    "                que.append((x, y-1))\n",
    "                que.append((x, y+1))\n",
    "                que.append((x-1, y-1))\n",
    "                que.append((x-1, y+1))\n",
    "                que.append((x+1, y+1))\n",
    "                que.append((x+1, y-1))\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def check(i,j):\n",
    "            if i<0 or j<0 or i>len(board)-1 or j > len(board[0])-1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        neighbors = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]\n",
    "        Minecount = [[0]*len(board[0]) for _ in board]\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if check(i,j):\n",
    "                    for neighbor in neighbors:\n",
    "                        if check(i+neighbor[0],j+neighbor[1]) and board[i+neighbor[0]][j+neighbor[1]] == 'M':\n",
    "                            Minecount[i][j] += 1\n",
    "\n",
    "        i,j = click[0],click[1]\n",
    "        if board[i][j] == 'M':\n",
    "            board[i][j] = 'X'\n",
    "            return board\n",
    "        elif board[i][j] == 'E':\n",
    "            if Minecount[i][j] > 0:\n",
    "                board[i][j] = str(Minecount[i][j])\n",
    "                return board\n",
    "            else:\n",
    "                board[i][j] = 'B'\n",
    "                process = [[i,j]] \n",
    "                while(process):\n",
    "                    ti,tj = process.pop()\n",
    "                    for neighbor in neighbors:\n",
    "                        if check(ti+neighbor[0],tj+neighbor[1]) and board[ti+neighbor[0]][tj+neighbor[1]] == 'E':\n",
    "                            if Minecount[ti+neighbor[0]][tj+neighbor[1]] > 0:\n",
    "                                board[ti+neighbor[0]][tj+neighbor[1]] = str(Minecount[ti+neighbor[0]][tj+neighbor[1]])\n",
    "                            else:\n",
    "                                process.append([ti+neighbor[0],tj+neighbor[1]])\n",
    "                                board[ti+neighbor[0]][tj+neighbor[1]] = 'B'\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        r, c = click\n",
    "        if board[r][c] == 'M':\n",
    "            board[r][c] = 'X'\n",
    "            return board\n",
    "\n",
    "        def dfs(i, j):\n",
    "            cnt = 0\n",
    "            for x in (-1, 0, 1):\n",
    "                for y in (-1, 0 ,1):\n",
    "                    r, c = i + x, j + y\n",
    "                    if 0<=r<m and 0<=c<n and board[r][c] == 'M':\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        \n",
    "        q = [click]\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for i, j in tmp:\n",
    "                cnt = dfs(i, j)\n",
    "                if cnt > 0:\n",
    "                    board[i][j] = str(cnt)\n",
    "                    continue\n",
    "                for x in (-1, 0, 1):\n",
    "                    for y in (-1, 0 ,1):\n",
    "                        ix, jy = i + x, j + y\n",
    "                        if 0<=ix<m and 0<=jy<n and board[ix][jy] == 'E':\n",
    "                            board[ix][jy] = 'B'\n",
    "                            q.append((ix, jy))\n",
    "\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def BFS(start):\n",
    "            queue = collections.deque()\n",
    "            queue.append(start)\n",
    "            while queue:\n",
    "                nx, ny = queue.popleft()\n",
    "                lei_count = 0\n",
    "                # 若周围都是空白\n",
    "                for x, y in [(nx+1, ny), (nx-1, ny),(nx, ny+1),(nx, ny-1),\\\n",
    "                    (nx+1, ny+1),(nx+1, ny-1),(nx-1, ny-1),(nx-1, ny+1)]:\n",
    "                    if 0 <= x < len(board) and 0 <= y < len(board[0]) \\\n",
    "                        and board[x][y] == \"M\":\n",
    "                        lei_count += 1\n",
    "                if lei_count == 0:\n",
    "                    board[nx][ny] = \"B\"\n",
    "                    for x, y in [(nx+1, ny), (nx-1, ny),(nx, ny+1),(nx, ny-1),\\\n",
    "                    (nx+1, ny+1),(nx+1, ny-1),(nx-1, ny-1),(nx-1, ny+1)]:\n",
    "                        if 0 <= x < len(board) and 0 <= y < len(board[0]) \\\n",
    "                            and board[x][y] == \"E\" :\n",
    "                            board[x][y] = \"B\" # 要被点开，修改成\"B\"\n",
    "                            queue.append((x, y))\n",
    "                else:\n",
    "                    board[nx][ny] = str(lei_count)\n",
    "            return board\n",
    "        # 如果踩雷\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "        return BFS(tuple(click))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        def inArea(x, y):\n",
    "            return 0 <= x < m and 0 <= y < n\n",
    "\n",
    "        stack = [(click[0], click[1])]\n",
    "        while stack:\n",
    "            x, y = stack.pop()\n",
    "            if board[x][y] != 'M' and board[x][y] != 'E': continue\n",
    "            if board[x][y] == 'M':\n",
    "                board[x][y] = 'X'\n",
    "                break\n",
    "            count = 0\n",
    "            toAppend = []\n",
    "            for dx in range(-1, 2):\n",
    "                for dy in range(-1, 2):\n",
    "                    if dx == 0 and dy == 0: continue\n",
    "                    nx = x + dx\n",
    "                    ny = y + dy\n",
    "                    if inArea(nx, ny):\n",
    "                        toAppend.append((nx, ny))\n",
    "                        if board[nx][ny] == 'M':\n",
    "                            count += 1\n",
    "            if count == 0:\n",
    "                board[x][y] = 'B'\n",
    "                stack += toAppend\n",
    "            else:\n",
    "                board[x][y] = str(count)\n",
    "\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        # bfs\n",
    "        x, y = click[0], click[1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return board\n",
    "        row, col = len(board), len(board[0])\n",
    "        if 'M' not in set(sum(board, [])):\n",
    "            return [['B' for _ in range(col)] for _ in range(row)]\n",
    "        vst = [[False for _ in range(col)] for _ in range(row)]\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]]\n",
    "        \n",
    "        que = collections.deque()\n",
    "        que.append((x, y))\n",
    "        while que:\n",
    "            cx, cy = que.popleft()\n",
    "            bomb_adjacent = []\n",
    "            next_lst = []\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = cx + dx, cy + dy\n",
    "                if nx < 0 or ny < 0 or nx >= row or ny >= col:\n",
    "                    continue\n",
    "                if not vst[nx][ny]:\n",
    "                    next_lst.append((nx, ny))\n",
    "                    if board[nx][ny] == 'M':\n",
    "                        bomb_adjacent.append((nx, ny))\n",
    "            if not bomb_adjacent:\n",
    "                board[cx][cy] = 'B'\n",
    "                que.extend(next_lst)\n",
    "            else:\n",
    "                board[cx][cy] = str(len(bomb_adjacent))\n",
    "            vst[cx][cy] = True\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        x,y = click\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        if board[x][y] == \"M\":\n",
    "            board[x][y] = \"X\"\n",
    "            return board\n",
    "        else:\n",
    "            margin = set()\n",
    "            dir_tuple = ((1,0),(0,1),(-1, 0),(0,-1),(-1,1),(1,1),(1,-1),(-1,-1))\n",
    "            gird = [[board[i][j] for j in range(n) ]  for i in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if gird[i][j] == \"M\":\n",
    "                        for px,py in dir_tuple:\n",
    "                            nx, ny = px+i,py+j\n",
    "                            if 0<=nx<m and 0<=ny<n:\n",
    "                                margin.add((nx,ny))\n",
    "                                if gird[nx][ny]!=\"M\":\n",
    "                                    if isinstance(gird[nx][ny], str):\n",
    "                                        gird[nx][ny] = 1\n",
    "                                    else:\n",
    "                                        gird[nx][ny] +=1\n",
    "            # print(gird)\n",
    "            the_click =  (x,y)\n",
    "            if the_click in margin:\n",
    "                board[x][y] = str(gird[x][y])\n",
    "                return board\n",
    "            else:\n",
    "                board[x][y] = \"B\"\n",
    "            point_list  = [the_click]\n",
    "            visit = {the_click}\n",
    "            while point_list:\n",
    "                temp = []\n",
    "                for i,j in point_list:\n",
    "                    for px,py in dir_tuple:\n",
    "                        nx, ny = px+i,py+j\n",
    "                        if 0<=nx<m and 0<=ny<n and (t:=(nx,ny)) not in visit:\n",
    "                            visit.add(t)\n",
    "                            if board[nx][ny] != gird[nx][ny]:\n",
    "                                board[nx][ny] = str(gird[nx][ny])\n",
    "                            elif board[nx][ny] == \"E\":\n",
    "                                board[nx][ny] = \"B\"\n",
    "                            else:\n",
    "                                continue\n",
    "                            if t not in margin:\n",
    "                                temp.append(t)\n",
    "                point_list = temp\n",
    "            return board\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        x,y = click\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        if board[x][y] == \"M\":\n",
    "            board[x][y] = \"X\"\n",
    "            return board\n",
    "        # elif board[x][y] == \"E\":\n",
    "        #     board[x][y] = \"B\"\n",
    "        #     point_list  = [(x,y)]\n",
    "        #     while point_list:\n",
    "        #         temp = []\n",
    "        #         for i,j in point_list:\n",
    "                    \n",
    "        else:\n",
    "            margin = set()\n",
    "            dir_tuple = ((1,0),(0,1),(-1, 0),(0,-1),(-1,1),(1,1),(1,-1),(-1,-1))\n",
    "            gird = [[board[i][j] for j in range(n) ]  for i in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if gird[i][j] == \"M\":\n",
    "                        for px,py in dir_tuple:\n",
    "                            nx, ny = px+i,py+j\n",
    "                            if 0<=nx<m and 0<=ny<n:\n",
    "                                margin.add((nx,ny))\n",
    "                                if gird[nx][ny]!=\"M\":\n",
    "                                    if isinstance(gird[nx][ny], str):\n",
    "                                        gird[nx][ny] = 1\n",
    "                                    else:\n",
    "                                        gird[nx][ny] +=1\n",
    "            # print(gird)\n",
    "            the_click =  (x,y)\n",
    "            if the_click in margin:\n",
    "                board[x][y] = str(gird[x][y])\n",
    "                return board\n",
    "            else:\n",
    "                board[x][y] = \"B\"\n",
    "            point_list  = [the_click]\n",
    "            visit = {the_click}\n",
    "            while point_list:\n",
    "                temp = []\n",
    "                for i,j in point_list:\n",
    "                    for px,py in dir_tuple:\n",
    "                        nx, ny = px+i,py+j\n",
    "                        if 0<=nx<m and 0<=ny<n and (t:=(nx,ny)) not in visit:\n",
    "                            visit.add(t)\n",
    "                            if board[nx][ny] != gird[nx][ny]:\n",
    "                                board[nx][ny] = str(gird[nx][ny])\n",
    "                            elif board[nx][ny] == \"E\":\n",
    "                                board[nx][ny] = \"B\"\n",
    "                            else:\n",
    "                                continue\n",
    "                            if t not in margin:\n",
    "                                temp.append(t)\n",
    "                point_list = temp\n",
    "            return board\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        d = [[-1,-1], [-1,0], [-1, 1],[0,1],[1,1],[1,0],[1,-1],[0,-1]]\n",
    "        Q = [click]\n",
    "        while Q:\n",
    "            r, c = Q.pop()\n",
    "            visited[r][c] = 1\n",
    "            q = []\n",
    "            ans = 0\n",
    "            for dr, dc in d:\n",
    "                nr, nc = dr +r , dc + c \n",
    "                if nr >=0 and nr < m and nc >= 0 and nc < n:\n",
    "                    if board[nr][nc] == 'M':\n",
    "                        ans += 1\n",
    "                    if not visited[nr][nc]:\n",
    "                        q.append([nr, nc])\n",
    "            if ans > 0:\n",
    "                board[r][c] = str(ans)\n",
    "            else:\n",
    "                board[r][c] = 'B'\n",
    "                Q = Q + q \n",
    "            \n",
    "        return board "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        direct = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]\n",
    "        r = len(board)\n",
    "        c = len(board[0])\n",
    "\n",
    "        def cal_around_M(x, y):\n",
    "            count = 0\n",
    "            for i, j in direct:\n",
    "                if x + i < 0 or x + i > r - 1 or y + j < 0 or y + j > c - 1:\n",
    "                    continue\n",
    "                if board[x + i][y + j] == 'M':\n",
    "                    count += 1\n",
    "            return count\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x > r - 1 or y < 0 or y > c - 1:\n",
    "                return\n",
    "            if board[x][y] != 'E':\n",
    "                return\n",
    "            count = cal_around_M(x, y)\n",
    "            if count != 0:\n",
    "                board[x][y] = str(count)\n",
    "                return\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for i, j in direct:\n",
    "                    dfs(x + i, y + j)\n",
    "\n",
    "        click_x, click_y = click\n",
    "        if board[click_x][click_y] == 'M':\n",
    "            board[click_x][click_y] = 'X'\n",
    "        else:\n",
    "            dfs(click_x, click_y)\n",
    "        return board\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, board, x, y):\n",
    "        cnt = 0\n",
    "        for i, j in self.direct:\n",
    "            if x + i < 0 or x + i >= self.row or y + j < 0 or y + j >= self.col:\n",
    "                continue\n",
    "            cnt += board[x + i][y + j] == 'M'\n",
    "        if cnt > 0:\n",
    "            board[x][y] = str(cnt)\n",
    "        else:\n",
    "            board[x][y] = 'B'\n",
    "            for i, j in self.direct:\n",
    "                if x + i < 0 or x + i >= self.row or y + j < 0 or y + j >= self.col or board[x + i][y + j] != 'E':\n",
    "                    continue\n",
    "                self.dfs(board, x + i, y + j)\n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        self.direct = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]\n",
    "        self.row = len(board)\n",
    "        self.col = len(board[0])\n",
    "        click_x, click_y = click\n",
    "        if board[click_x][click_y] == 'M':\n",
    "            board[click_x][click_y] = 'X'\n",
    "        else:\n",
    "            self.dfs(board, click_x, click_y)\n",
    "        return board\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, board, x, y):\n",
    "        q = deque([(x, y)])\n",
    "        vis = {(x, y)}\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            cnt = 0\n",
    "            for i, j in self.direct:\n",
    "                if x + i < 0 or x + i >= self.row or y + j < 0 or y + j >= self.col:\n",
    "                    continue\n",
    "                cnt += board[x + i][y + j] == 'M'\n",
    "            if cnt > 0:\n",
    "                board[x][y] = str(cnt)\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for i, j in self.direct:\n",
    "                    if (x + i < 0 or x + i >= self.row or y + j < 0 or y + j >= self.col or\n",
    "                            board[x + i][y + j] != 'E' or (x + i, y + j) in vis):\n",
    "                        continue\n",
    "                    q.append((x + i, y + j))\n",
    "                    vis.add((x + i, y + j))\n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        self.direct = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]\n",
    "        self.row = len(board)\n",
    "        self.col = len(board[0])\n",
    "        click_x, click_y = click\n",
    "        if board[click_x][click_y] == 'M':\n",
    "            board[click_x][click_y] = 'X'\n",
    "        else:\n",
    "            self.bfs(board, click_x, click_y)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board, click):\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "\n",
    "        if board[click[0]][click[1]] == \"B\":\n",
    "            return board\n",
    "\n",
    "        # 只在点击到未操作的非雷格时，才进行处理~\n",
    "        q = deque()\n",
    "        q.append(click)\n",
    "        visited = []\n",
    "\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            visited.append(cur)\n",
    "\n",
    "            if cur[0] < 0 or cur[0] >= len(board):\n",
    "                continue\n",
    "            if cur[1] < 0 or cur[1] >= len(board[0]):\n",
    "                continue\n",
    "\n",
    "            mines_num = get_mines_num(board, cur)\n",
    "\n",
    "            if board[cur[0]][cur[1]] == \"E\":\n",
    "                if mines_num:\n",
    "                    board[cur[0]][cur[1]] = str(mines_num)\n",
    "                else:\n",
    "                    board[cur[0]][cur[1]] = \"B\"\n",
    "                    items = [[cur[0] + i, cur[1] + j] for i in (-1, 0, 1) for j in (-1, 0, 1)]\n",
    "                    for item in items:\n",
    "                        if item[0] < 0 or item[0] >= len(board):\n",
    "                            continue\n",
    "                        if item[1] < 0 or item[1] >= len(board[0]):\n",
    "                            continue\n",
    "                        if item not in visited:\n",
    "                            q.append(item)\n",
    "\n",
    "        return board\n",
    "\n",
    "\n",
    "def get_mines_num(board, pos):\n",
    "    counter = 0\n",
    "    for i in (-1, 0, 1):\n",
    "        for j in (-1, 0, 1):\n",
    "            row = pos[0] + i\n",
    "            col = pos[1] + j\n",
    "            if row < 0 or row >= len(board):\n",
    "                continue\n",
    "            if col < 0 or col >= len(board[0]):\n",
    "                continue\n",
    "\n",
    "            if board[row][col] == \"M\":\n",
    "                counter += 1\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, board, x,y):\n",
    "        dirx = [0,0,1,1,1,-1,-1,-1]\n",
    "        diry = [1,-1,0,1,-1,0,1,-1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return\n",
    "        if board[x][y] == 'E':\n",
    "            cnt = 0\n",
    "            for i in range(8):\n",
    "                tx = x + dirx[i]\n",
    "                ty = y + diry[i]\n",
    "                if 0 <= tx < len(board) and 0 <= ty < len(board[0]):\n",
    "                    if board[tx][ty] == 'M':\n",
    "                        cnt += 1\n",
    "            if cnt != 0:\n",
    "                board[x][y] = str(cnt)\n",
    "                return\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for i in range(8):\n",
    "                    tx = x + dirx[i]\n",
    "                    ty = y + diry[i]\n",
    "                    if 0 <= tx < len(board) and 0 <= ty < len(board[0]):\n",
    "                        self.dfs(board, tx, ty)\n",
    "\n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        self.dfs(board,click[0],click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m,n = len(board),len(board[0])\n",
    "        r,c = click\n",
    "        if board[r][c] =='M':\n",
    "            board[r][c] = 'X'\n",
    "            return board\n",
    "        dirs = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        def check_num(x,y):\n",
    "            res = 0\n",
    "            for dx,dy in dirs:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if nx <0 or nx>=m or ny<0 or ny>=n: continue\n",
    "                if board[nx][ny] == 'M':res += 1\n",
    "            return res\n",
    "        cur = check_num(r,c)\n",
    "        if cur:\n",
    "            board[r][c] = str(cur)\n",
    "            return board\n",
    "        def dfs(x,y):\n",
    "            board[x][y] = 'B'\n",
    "            for dx,dy in dirs[:4]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if nx <0 or nx>=m or ny<0 or ny>=n or board[nx][ny]!='E' : continue\n",
    "                num = check_num(nx,ny)\n",
    "                if num:\n",
    "                    board[nx][ny] = str(num)\n",
    "                else:\n",
    "                    dfs(nx,ny)\n",
    "            for dx,dy in dirs[-4:]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if nx <0 or nx>=m or ny<0 or ny>=n or board[nx][ny]!='E' : continue\n",
    "                num = check_num(nx,ny)\n",
    "                if num:\n",
    "                    board[nx][ny] = str(num)\n",
    "\n",
    "        dfs(r,c)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "                                  \n",
    "        def calc(r, c):\n",
    "            val = 0\n",
    "            for x, y in dirs:\n",
    "                i, j = x + r, y + c\n",
    "                if 0 <= i < m and 0 <= j < n and board[i][j] == 'M': val += 1\n",
    "            return val\n",
    "\n",
    "        def dfs(r, c):\n",
    "            cnt = calc(r, c)\n",
    "            if cnt == 0:\n",
    "                board[r][c] = 'B'\n",
    "                for x, y in dirs:\n",
    "                    i, j = x + r, y + c\n",
    "                    if 0 <= i < m and 0 <= j < n and board[i][j] == 'E': \n",
    "                        dfs(i, j)\n",
    "            else: board[r][c] = str(cnt)\n",
    "\n",
    "        def bfs(r, c):\n",
    "            q = deque([(r, c)])\n",
    "            while q:                                \n",
    "                r, c = q.popleft()\n",
    "                cnt = calc(r, c)\n",
    "                if cnt == 0:\n",
    "                    board[r][c] = 'B'\n",
    "                    for x, y in dirs:\n",
    "                        i, j = x + r, y + c\n",
    "                        if 0 <= i < m and 0 <= j < n and board[i][j] == 'E': \n",
    "                            q.append((i, j))\n",
    "                            board[i][j] = '*' # 先标记一下，表示访问过，后面会更新，否则超时。\n",
    "                else: board[r][c] = str(cnt)\n",
    "                    \n",
    "            \n",
    "        dirs = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]\n",
    "        m, n = len(board), len(board[0])        \n",
    "        r, c = click\n",
    "        if board[r][c] == 'M': board[r][c] = 'X'\n",
    "        else: \n",
    "            bfs(r, c)\n",
    "            #dfs(r, c)\n",
    "            \n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        self.nr, self.nc = len(board), len(board[0])\n",
    "        # up_left, up, up_right, right, down_right, down, down_left, left \n",
    "        self.direction = [(-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0)]\n",
    "        # self.visited = [[0] * self.nc for _ in range(self.nr)]\n",
    "\n",
    "        x, y = click[0], click[1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "        else:\n",
    "            self.dfs(board, x, y)\n",
    "        return board\n",
    "\n",
    "    def dfs(self, board, x, y):\n",
    "        if x < 0 or x == self.nr or y < 0 or y == self.nc:\n",
    "            return\n",
    "        if board[x][y] != 'E': # 'B', digit\n",
    "            return\n",
    "\n",
    "        cnt = 0\n",
    "        for dx, dy in self.direction:\n",
    "            tx, ty = x + dx, y + dy\n",
    "            if tx < 0 or tx == self.nr or ty < 0 or ty == self.nc:\n",
    "                continue\n",
    "            if board[tx][ty] == 'M':\n",
    "                cnt += 1\n",
    "        if cnt > 0: # find mine(s), no need for recursion\n",
    "            board[x][y] = str(cnt)\n",
    "            return\n",
    "        else:\n",
    "            board[x][y] = 'B'\n",
    "            for dx, dy in self.direction:\n",
    "                self.dfs(board, x + dx, y + dy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, board, x,y,visited):\n",
    "        dirx = [0,0,1,1,1,-1,-1,-1]\n",
    "        diry = [1,-1,0,1,-1,0,1,-1]\n",
    "        if (x, y) in visited:\n",
    "            return\n",
    "        visited.add((x,y))\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return\n",
    "        if board[x][y] == 'E':\n",
    "            cnt = 0\n",
    "            for i in range(8):\n",
    "                tx = x + dirx[i]\n",
    "                ty = y + diry[i]\n",
    "                if 0 <= tx < len(board) and 0 <= ty < len(board[0]):\n",
    "                    if board[tx][ty] == 'M':\n",
    "                        cnt += 1\n",
    "            if cnt != 0:\n",
    "                board[x][y] = str(cnt)\n",
    "                return\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for i in range(8):\n",
    "                    tx = x + dirx[i]\n",
    "                    ty = y + diry[i]\n",
    "                    if 0 <= tx < len(board) and 0 <= ty < len(board[0]):\n",
    "                        self.dfs(board, tx, ty, visited)\n",
    "\n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        visited = set()\n",
    "        self.dfs(board,click[0],click[1],visited)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        iCnt = 0\n",
    "        block = []\n",
    "        for l in [[0,1],[0,-1],[1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]:\n",
    "            new_i,new_j = click[0]+l[0],click[1]+l[1]\n",
    "            if 0 <= new_i < len(board) and 0 <= new_j < len(board[0]):\n",
    "                if board[new_i][new_j] == 'M':\n",
    "                    iCnt += 1\n",
    "                elif board[new_i][new_j] == 'E':\n",
    "                    block.append([new_i,new_j])\n",
    "        if iCnt:\n",
    "            board[click[0]][click[1]] = str(iCnt)\n",
    "        else:\n",
    "            board[click[0]][click[1]] = 'B'\n",
    "            for l in block:\n",
    "                self.updateBoard(board,l)\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        i, j = click[0], click[1]\n",
    "        if board[i][j] == 'M':\n",
    "            board[i][j] = 'X'\n",
    "            return board\n",
    "        if board[i][j] == 'E':\n",
    "            self._updateE(board, i, j)\n",
    "            return board\n",
    "        return board\n",
    "    \n",
    "    def _updateE(self, board, i, j):\n",
    "        board[i][j], count = 'B', 0\n",
    "        for ki in [-1, 0, 1]:\n",
    "            for kj in [-1, 0, 1]:\n",
    "                if 0 <= i+ki < len(board) and 0 <= j+kj < len(board[0]):\n",
    "                    if board[i+ki][j+kj] == \"M\":\n",
    "                        count += 1\n",
    "        \n",
    "        if count > 0:\n",
    "            board[i][j] = str(count)\n",
    "            return\n",
    "        \n",
    "        for ki in [-1, 0, 1]:\n",
    "            for kj in [-1, 0, 1]:\n",
    "                if 0 <= i+ki < len(board) and 0 <= j+kj < len(board[0]):\n",
    "                    if board[i+ki][j+kj] == 'E':\n",
    "                        self._updateE(board, i+ki, j+kj)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        x, y = click[0], click[1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return board\n",
    "        self.helper(x, y, board)\n",
    "        return board\n",
    "    \n",
    "    def helper(self, x, y, board):\n",
    "        if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]):\n",
    "            return\n",
    "        curr = board[x][y]\n",
    "        if curr == 'M':\n",
    "            return\n",
    "        elif curr == 'E':\n",
    "            cnt = self.count(x, y, board)\n",
    "            if cnt > 0:\n",
    "                board[x][y] = str(cnt)\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                self.helper(x+1, y, board)\n",
    "                self.helper(x-1, y, board)\n",
    "                self.helper(x, y+1, board)\n",
    "                self.helper(x, y-1, board)\n",
    "                self.helper(x+1, y-1, board)\n",
    "                self.helper(x+1, y+1, board)\n",
    "                self.helper(x-1, y-1, board)\n",
    "                self.helper(x-1, y+1, board)\n",
    "\n",
    "        # num or B\n",
    "        return\n",
    "\n",
    "    \n",
    "    def count(self, x, y, board):\n",
    "        cnt = 0\n",
    "        if x + 1 < len(board) and board[x+1][y] == 'M':\n",
    "            cnt += 1 \n",
    "        if x + 1 < len(board) and y + 1 < len(board[0]) and board[x+1][y+1] == 'M':\n",
    "            cnt += 1\n",
    "        if x - 1 >= 0 and board[x-1][y] == 'M':\n",
    "            cnt += 1\n",
    "        if x - 1 >= 0 and y + 1 < len(board[0]) and board[x-1][y+1] == 'M':\n",
    "            cnt += 1\n",
    "        if y + 1 < len(board[0]) and board[x][y+1] == 'M':\n",
    "            cnt += 1\n",
    "        if x + 1 < len(board) and y - 1 >= 0 and board[x+1][y-1] == 'M':\n",
    "            cnt += 1\n",
    "        if y - 1 >= 0 and board[x][y-1] == 'M':\n",
    "            cnt += 1\n",
    "        if x - 1 >= 0 and y - 1 >= 0 and board[x-1][y-1] == 'M':\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]]!='M' and board[click[0]][click[1]]!='E':\n",
    "            # 已揭露\n",
    "            return board\n",
    "\n",
    "        if board[click[0]][click[1]]=='M':\n",
    "            # 规则1\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        \n",
    "        def haveM(board,click):\n",
    "            n,m = len(board),len(board[0])\n",
    "            x,y = click\n",
    "            direct = [(x+1,y+1),(x-1,y-1),(x+1,y),(x-1,y),(x,y+1),(x,y-1),(x-1,y+1),(x+1,y-1)]\n",
    "            flag = 0\n",
    "            \n",
    "            for new_x,new_y in direct:\n",
    "                if 0<=new_x<n and 0<=new_y<m and board[new_x][new_y]=='M':\n",
    "                    flag+=1\n",
    "            return flag\n",
    "        \n",
    "        # 显示数字(规则3)\n",
    "        flag = haveM(board,click)\n",
    "        if flag:\n",
    "            board[click[0]][click[1]] = '{}'.format(flag)\n",
    "            return board\n",
    "        # 递归揭示(规则2)\n",
    "        board[click[0]][click[1]] = 'B'\n",
    "        x,y = click\n",
    "        n, m = len(board), len(board[0])\n",
    "        direct = [(x+1,y+1),(x-1,y-1),(x+1,y),(x-1,y),(x,y+1),(x,y-1),(x-1,y+1),(x+1,y-1)]\n",
    "        for new_x,new_y in direct:\n",
    "            if 0<=new_x<n and 0<=new_y<m:\n",
    "                board = self.updateBoard(board,[new_x,new_y])\n",
    "        return board\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]]!='M' and board[click[0]][click[1]]!='E':\n",
    "            # 已揭露\n",
    "            return board\n",
    "\n",
    "        if board[click[0]][click[1]]=='M':\n",
    "            # 规则1\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        \n",
    "        def haveM(board,click):\n",
    "            n,m = len(board),len(board[0])\n",
    "            x,y = click\n",
    "            direct = [(x+1,y+1),(x-1,y-1),(x+1,y),(x-1,y),(x,y+1),(x,y-1),(x-1,y+1),(x+1,y-1)]\n",
    "            flag = 0\n",
    "            \n",
    "            for new_x,new_y in direct:\n",
    "                if 0<=new_x<n and 0<=new_y<m and board[new_x][new_y]=='M':\n",
    "                    flag+=1\n",
    "            return flag\n",
    "        \n",
    "        # 显示数字(规则3)\n",
    "        flag = haveM(board,click)\n",
    "        if flag:\n",
    "            board[click[0]][click[1]] = '{}'.format(flag)\n",
    "            return board\n",
    "        # 递归揭示(规则2)\n",
    "        board[click[0]][click[1]] = 'B'\n",
    "        x,y = click\n",
    "        n, m = len(board), len(board[0])\n",
    "        direct = [(x+1,y+1),(x-1,y-1),(x+1,y),(x-1,y),(x,y+1),(x,y-1),(x-1,y+1),(x+1,y-1)]\n",
    "        for new_x,new_y in direct:\n",
    "            if 0<=new_x<n and 0<=new_y<m:\n",
    "                board = self.updateBoard(board,[new_x,new_y])\n",
    "        return board\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def dfs(board,x,y):\n",
    "            count = 0\n",
    "            for i in range(x-1,x+2):\n",
    "                for j in range(y-1,y+2):\n",
    "                    if 0<=i<len(board) and 0<=j<len(board[0]) and board[i][j] == 'M':\n",
    "                        count+=1\n",
    "                    \n",
    "            if count > 0:\n",
    "                board[x][y] = str(count)\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for i in range(x-1,x+2):\n",
    "                    for j in range(y-1,y+2):\n",
    "                        if 0<=i<len(board) and 0<=j<len(board[0]) and board[i][j] == 'E':\n",
    "                            dfs(board,i,j)\n",
    "\n",
    "        x ,y = click[0],click[1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "        else:\n",
    "            dfs(board,x,y)\n",
    "        return board\n",
    "\n",
    "\n",
    "                     \n",
    "                   \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.direction = [(0, -1), (0, 1), (-1, 0), (1, 0), \n",
    "                    (-1, -1), (1, 1), (-1, 1), (1, -1)] \n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "        if board[click[0]][click[1]] == \"E\":\n",
    "            num = self.getMinesNum(board, click[0], click[1])\n",
    "            if num == 0:\n",
    "                self.checkSquare(board, click[0], click[1], len(board), len(board[0]))\n",
    "            else:\n",
    "                board[click[0]][click[1]] = str(num)\n",
    "                return board\n",
    "        return board\n",
    "\n",
    "    def getMinesNum(self, board, x, y):\n",
    "        n, m = len(board), len(board[0])\n",
    "        countNum = 0\n",
    "        for x0, y0 in self.direction:\n",
    "            if 0 <= x+x0 < n and 0 <= y+y0 < m:\n",
    "                if board[x+x0][y+y0] == \"M\":\n",
    "                    countNum += 1\n",
    "        return countNum\n",
    "\n",
    "    def checkSquare(self, board, x, y, n, m):\n",
    "        num = self.getMinesNum(board, x, y)\n",
    "        if num != 0:\n",
    "            board[x][y] = str(num)\n",
    "            return\n",
    "        board[x][y] = \"B\"\n",
    "        for x0, y0 in self.direction:\n",
    "            if 0 <= x+x0 < n and 0 <= y+y0 < m and board[x+x0][y+y0] == \"E\":\n",
    "                # print(\"{} {}\".format(x+x0, y+y0))\n",
    "                self.checkSquare(board, x+x0, y+y0, n, m)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        direction = [(-1, -1), (-1, 0), (-1, 1),\n",
    "                     (0, -1), (0, 1),\n",
    "                     (1, -1), (1, 0), (1, 1)]\n",
    "\n",
    "        def searchAround(x,y, board): #看看周围几个雷\n",
    "            count=0\n",
    "            m, n = len(board), len(board[0])\n",
    "            for i,j in direction:\n",
    "                if 0<=x+i<=m-1 and 0<=y+j<=n-1:\n",
    "                    if board[x+i][y+j]=='M':\n",
    "                        count+=1\n",
    "            return count\n",
    "\n",
    "        def dfs(x, y, board):\n",
    "            m, n = len(board), len(board[0])\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return\n",
    "            if board[x][y] != 'E':\n",
    "                return\n",
    "            count = searchAround(x, y, board)\n",
    "            if count != 0:\n",
    "                board[x][y] = str(count)\n",
    "                return\n",
    "            else:\n",
    "                board[x][y]='B'\n",
    "                for i,j in direction:\n",
    "                    dfs(x+i,y+j, board)\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        else:\n",
    "            dfs(click[0], click[1], board)\n",
    "            return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] != 'M' and board[click[0]][click[1]] != 'E':\n",
    "            # 已揭露\n",
    "            return board\n",
    "        n, m = len(board), len(board[0])\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            # 规则1\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "\n",
    "        def haveM(board, click):\n",
    "            \n",
    "            x, y = click\n",
    "            direct = [(x + 1, y + 1), (x - 1, y - 1), (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1), (x - 1, y + 1),(x + 1, y - 1)]\n",
    "            flag = 0\n",
    "\n",
    "            for new_x, new_y in direct:\n",
    "                if 0 <= new_x < n and 0 <= new_y < m and board[new_x][new_y] == 'M':\n",
    "                    flag += 1\n",
    "            return flag\n",
    "\n",
    "        # 显示数字\n",
    "        flag = haveM(board, click)\n",
    "        if flag:\n",
    "            board[click[0]][click[1]] = '{}'.format(flag)\n",
    "            return board\n",
    "        board[click[0]][click[1]] = 'B'\n",
    "        x, y = click\n",
    "        \n",
    "        direct = [(x + 1, y + 1), (x - 1, y - 1), (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1), (x - 1, y + 1),(x + 1, y - 1)]\n",
    "        for new_x, new_y in direct:\n",
    "            if 0 <= new_x < n and 0 <= new_y < m:\n",
    "                board = self.updateBoard(board, [new_x, new_y])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = click[0]\n",
    "        n = click[1]\n",
    "        if board[m][n] == 'M':\n",
    "            board[m][n] = 'X'\n",
    "            return board\n",
    "        self.help((m, n), board)\n",
    "        return board\n",
    "\n",
    "    def help(self, t, board):\n",
    "        i, j = t\n",
    "        if board[i][j] != 'E':\n",
    "            return\n",
    "        count = 0\n",
    "        for f in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)):\n",
    "            x = i + f[0]\n",
    "            y = j + f[1]\n",
    "            if 0 <= x < len(board) and 0 <= y < len(board[0]):\n",
    "                if board[x][y] == 'M':\n",
    "                    count += 1\n",
    "\n",
    "        if count > 0:\n",
    "            board[i][j] = str(count)\n",
    "            return\n",
    "        else:\n",
    "            board[i][j] = 'B'\n",
    "            for f in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)):\n",
    "                x = i + f[0]\n",
    "                y = j + f[1]\n",
    "                if 0 <= x < len(board) and 0 <= y < len(board[0]):\n",
    "                    self.help((x, y), board)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = click[0]\n",
    "        n = click[1]\n",
    "        self.f = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1))\n",
    "        if board[m][n] == 'M':\n",
    "            board[m][n] = 'X'\n",
    "            return board\n",
    "        self.helper((m, n), board)\n",
    "        return board\n",
    "\n",
    "    def helper(self, t, board):\n",
    "        i, j = t\n",
    "        if board[i][j] != 'E':\n",
    "            return\n",
    "        count = 0\n",
    "        for dx, dy in self.f:\n",
    "            x, y = i + dx, j + dy\n",
    "            if 0 <= x < len(board) and 0 <= y < len(board[0]):\n",
    "                if board[x][y] == 'M':\n",
    "                    count += 1\n",
    "        if count != 0:\n",
    "            board[i][j] = str(count)\n",
    "            return\n",
    "        else:\n",
    "            board[i][j] = 'B'\n",
    "            for dx, dy in self.f:\n",
    "                x, y = i + dx, j + dy\n",
    "                if 0 <= x < len(board) and 0 <= y < len(board[0]):\n",
    "                    self.helper((x, y), board)\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        direct=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        def dfs(board,i,j,m,n):\n",
    "            cnt=0\n",
    "            for d in direct:\n",
    "                x=i+d[0]\n",
    "                y=j+d[1]\n",
    "                if 0<=x<m and 0<=y<n and board[x][y]=='M':\n",
    "                    cnt+=1\n",
    "            if cnt>0 and board[i][j]=='E':\n",
    "                board[i][j]=str(cnt)\n",
    "            else:\n",
    "                board[i][j]='B'\n",
    "                for d1 in direct:\n",
    "                    x1=i+d1[0]\n",
    "                    y1=j+d1[1]\n",
    "                    if 0<=x1<m and 0<=y1<n and board[x1][y1]=='E':\n",
    "                        dfs(board,x1,y1,m,n)\n",
    "        i=click[0]\n",
    "        j=click[1]\n",
    "        if board[i][j]=='M':\n",
    "            board[i][j]='X'\n",
    "        else:\n",
    "            dfs(board,i,j,m,n)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        nums = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        visit = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"M\":\n",
    "                    near = [[i+1,j],[i-1,j],[i+1,j+1],[i+1,j-1],[i-1,j+1],[i-1,j-1],[i,j+1],[i,j-1]]\n",
    "                    for k1,k2 in near:\n",
    "                        if 0<=k1<=m-1 and 0<=k2<=n-1:\n",
    "                            nums[k1][k2] += 1\n",
    "        \n",
    "                    \n",
    "\n",
    "        def dfs(i,j):\n",
    "            if i<0 or i>=m or j<0 or j>=n or board[i][j] == \"M\":\n",
    "                return\n",
    "            if visit[i][j]==1: return\n",
    "            visit[i][j] = 1\n",
    "            \n",
    "            if nums[i][j] == 0:\n",
    "                board[i][j] = \"B\"\n",
    "                dfs(i+1,j)\n",
    "                dfs(i-1,j)\n",
    "                dfs(i,j+1)\n",
    "                dfs(i,j-1)\n",
    "                dfs(i+1,j+1)\n",
    "                dfs(i-1,j-1)\n",
    "                dfs(i+1,j-1)\n",
    "                dfs(i-1,j+1)\n",
    "            else:\n",
    "                board[i][j] = str(nums[i][j])\n",
    "            return\n",
    "        \n",
    "            \n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "        else:    \n",
    "            dfs(click[0],click[1])\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def border_mine(v):\n",
    "            x, y = v[0], v[1]\n",
    "            mine_c = 0\n",
    "            for dx, dy in Direct:\n",
    "                next_x, next_y = x + dx, y + dy\n",
    "                if 0 <= next_x < m and 0 <= next_y < n and board[next_x][next_y] == \"M\":\n",
    "                    mine_c += 1\n",
    "            return (True, mine_c) if mine_c > 0 else (False, 0)\n",
    "\n",
    "        def dfs(v):\n",
    "            x, y = v[0], v[1]\n",
    "            visited[x][y] = True\n",
    "            if board[x][y] == \"M\":\n",
    "                board[x][y] = \"X\"\n",
    "                return\n",
    "            elif board[x][y] == \"E\":\n",
    "                have_mine, mine_c = border_mine(v)\n",
    "                if have_mine:\n",
    "                    board[x][y] = str(mine_c)\n",
    "                    return\n",
    "                else:\n",
    "                    board[x][y] = \"B\"\n",
    "                    for dx, dy in Direct:\n",
    "                        next_x, next_y = x + dx, y + dy\n",
    "                        if 0 <= next_x < m and 0 <= next_y < n and visited[next_x][next_y] == False:\n",
    "                            w = (next_x, next_y)\n",
    "                            dfs(w)\n",
    "            else:\n",
    "                return\n",
    "\n",
    "        def bfs(s):\n",
    "            q=deque()\n",
    "            q.append(s)\n",
    "            visited[s[0]][s[1]]=True\n",
    "            while q:\n",
    "                x,y = q.popleft()\n",
    "\n",
    "                if board[x][y] == \"M\":\n",
    "                    board[x][y] = \"X\"\n",
    "                    # return\n",
    "                elif board[x][y] == \"E\":\n",
    "                    have_mine, mine_c = border_mine((x,y))\n",
    "                    if have_mine:\n",
    "                        board[x][y] = str(mine_c)\n",
    "                        # return\n",
    "                    else:\n",
    "                        board[x][y] = \"B\"\n",
    "                        for dx, dy in Direct:\n",
    "                            next_x, next_y = x + dx, y + dy\n",
    "                            if 0 <= next_x < m and 0 <= next_y < n and visited[next_x][next_y] == False:\n",
    "                                w = (next_x, next_y)\n",
    "                                q.append(w)\n",
    "                                visited[next_x][next_y] = True\n",
    "                else:\n",
    "                    # return\n",
    "                    pass\n",
    "\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        Direct = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (1, -1), (-1, 1), (1, 1)]\n",
    "        # dfs((click[0], click[1]))\n",
    "        bfs((click[0], click[1]))\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        rows, cols = len(board), len(board[0])\n",
    "        clickR, clickC = click\n",
    "        # 比普通的二维数组数组遍历，neigh更多\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "\n",
    "        # 判断 [r, c] 点周边有几个雷\n",
    "        def getNeighMineCount(r, c):\n",
    "            count = 0\n",
    "            for dr,dc in directions:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                if nr in range(rows) and nc in range(cols) and board[nr][nc] == 'M': count += 1\n",
    "            return count\n",
    "\n",
    "        def dfs(row, col):\n",
    "            # if r not in range(rows) or c not in range(cols): return False           \n",
    "            #     # 已知方块，直接返回\n",
    "            #     if board[r][c] != 'E': return board[r][c] == 'M'\n",
    "\n",
    "\n",
    "            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != 'E':\n",
    "                return\n",
    "            val = getNeighMineCount(row, col)\n",
    "            if val == 0:\n",
    "                board[row][col] = 'B'\n",
    "                for i in range(0, len(directions)):\n",
    "                    dfs(row + directions[i][0], col + directions[i][1])\n",
    "            else:\n",
    "                board[row][col] = str(val)\n",
    "\n",
    "        # 分情况讨论\n",
    "        # 刚好是地雷\n",
    "        if board[clickR][clickC] == 'M':\n",
    "            board[clickR][clickC] = 'X'\n",
    "        elif board[clickR][clickC] == 'E':\n",
    "        # 空方块的情况, 先判断「空方块周边是否有雷」\n",
    "            count = getNeighMineCount(clickR, clickC)\n",
    "            if count != 0:\n",
    "                board[clickR][clickC] = str(count)\n",
    "            else:\n",
    "                dfs(clickR, clickC)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]]=='M':\n",
    "            board[click[0]][click[1]]='X'\n",
    "            return board\n",
    "        elif board[click[0]][click[1]]!='E':\n",
    "            return board\n",
    "        dir = [[1,0],[0,1],[1,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]]\n",
    "        line = len(board)\n",
    "        col = len(board[0])\n",
    "        grid = [[0]*col for i in range(line)]\n",
    "        dfs_map = [[0]*col for i in range(line)]\n",
    "        shu = '1234567890'\n",
    "        for i in range(line):\n",
    "            for j in range(col):\n",
    "                if board[i][j]!='E':\n",
    "                    dfs_map[i][j]=1\n",
    "                    if board[i][j] in shu:\n",
    "                        grid[i][j]=int(board[i][j])\n",
    "                    elif board[i][j]=='M':\n",
    "                        grid[i][j]=-1\n",
    "        def dfs(position):\n",
    "            nonlocal grid\n",
    "            nonlocal dfs_map\n",
    "            if dfs_map[position[0]][position[1]]!=0:\n",
    "                return \n",
    "            dfs_map[position[0]][position[1]]=1\n",
    "            s = 0\n",
    "            for i in range(8):\n",
    "                x = position[0]+dir[i][0]\n",
    "                y = position[1]+dir[i][1]\n",
    "                if x>=0 and x<line and y>=0 and y<col:\n",
    "                    if grid[x][y]==-1:\n",
    "                        s+=1\n",
    "                    else:\n",
    "                        dfs([x,y])\n",
    "            grid[position[0]][position[1]]=s\n",
    "        dfs(click)\n",
    "        dfs_map2 = [[0]*col for i in range(line)]#标注能变成B的东西\n",
    "        def dfs2(position):\n",
    "            nonlocal dfs_map\n",
    "            nonlocal dfs_map2\n",
    "            nonlocal grid\n",
    "            if grid[position[0]][position[1]]!=0:\n",
    "                dfs_map2[position[0]][position[1]]=grid[position[0]][position[1]]\n",
    "                return\n",
    "            elif dfs_map2[position[0]][position[1]]!=0:\n",
    "                return\n",
    "            dfs_map2[position[0]][position[1]]=-1\n",
    "            for i in range(8):\n",
    "                x = position[0]+dir[i][0]\n",
    "                y = position[1]+dir[i][1]\n",
    "                if x>=0 and x<line and y>=0 and y<col:\n",
    "                    dfs2([x,y])\n",
    "        dfs2(click)\n",
    "        for i in range(line):\n",
    "            for j in range(col):\n",
    "                if dfs_map2[i][j]==-1:\n",
    "                    board[i][j]='B'\n",
    "                elif dfs_map2[i][j]!=0:\n",
    "                    board[i][j]=str(dfs_map2[i][j])\n",
    "        return board\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        rows, cols = len(board), len(board[0])\n",
    "        clickR, clickC = click\n",
    "        # 比普通的二维数组数组遍历，neigh更多\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "\n",
    "        # 判断 [r, c] 点周边有几个雷\n",
    "        def getNeighMineCount(r, c):\n",
    "            count = 0\n",
    "            for dr,dc in directions:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                if nr in range(rows) and nc in range(cols) and board[nr][nc] == 'M': count += 1\n",
    "            return count\n",
    "\n",
    "        def dfs(r, c):\n",
    "            # 越界\n",
    "            if r not in range(rows) or c not in range(cols): return           \n",
    "            # 已知方块，直接返回\n",
    "            if board[r][c] != 'E': return\n",
    "\n",
    "            count = getNeighMineCount(r, c)\n",
    "            # 周边有地雷再，改完 board 直接return\n",
    "            if count != 0:\n",
    "                board[r][c] = str(count)\n",
    "                return\n",
    "            \n",
    "            board[r][c] = 'B'\n",
    "            for dr,dc in directions: \n",
    "                nr, nc = r + dr, c + dc\n",
    "                dfs(nr, nc)\n",
    "                \n",
    "\n",
    "        # 分情况讨论\n",
    "        # 刚好是地雷\n",
    "        if board[clickR][clickC] == 'M':\n",
    "            board[clickR][clickC] = 'X'\n",
    "        elif board[clickR][clickC] == 'E':\n",
    "        # 空方块的情况, 先判断「空方块周边是否有雷」\n",
    "            count = getNeighMineCount(clickR, clickC)\n",
    "            if count != 0:\n",
    "                board[clickR][clickC] = str(count)\n",
    "            else:\n",
    "                dfs(clickR, clickC)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        def mine(board, i, j):\n",
    "            if i<0 or i>=row or j<0 or j>=col:\n",
    "                return 0\n",
    "            num = 0\n",
    "            if i-1>=0:\n",
    "                if j-1 >=0 and board[i-1][j-1] == 'M':\n",
    "                    num += 1\n",
    "                if board[i-1][j] == 'M':\n",
    "                    num += 1\n",
    "                if j+1 < col and board[i-1][j+1]=='M':\n",
    "                    num += 1\n",
    "            if j-1 >=0 and board[i][j-1]=='M':\n",
    "                num += 1\n",
    "            if j+1 < col and board[i][j+1]=='M':\n",
    "                num += 1\n",
    "            if i+1 < row:\n",
    "                \n",
    "                if j-1 >=0 and board[i+1][j-1]=='M':\n",
    "                    num += 1\n",
    "                if board[i+1][j]=='M':\n",
    "                    num += 1\n",
    "                if j+1<col and board[i+1][j+1]=='M':\n",
    "                    num += 1\n",
    "            if board[i][j] == 'M':\n",
    "                num += 1\n",
    "            return num\n",
    "\n",
    "        def backtrack(board, i,j):\n",
    "            if i < 0 or j >= col  or j < 0 or i  >= row or board[i][j] != 'E':\n",
    "                return \n",
    "            tmp = mine(board, i, j)\n",
    "            if tmp == 0 :\n",
    "                board[i][j] = 'B'\n",
    "                backtrack(board, i+1, j)\n",
    "                backtrack(board, i-1, j)\n",
    "                backtrack(board, i, j+1)\n",
    "                backtrack(board, i-1, j-1)               \n",
    "                backtrack(board, i-1, j+1)\n",
    "                backtrack(board, i, j-1)               \n",
    "                backtrack(board, i+1, j-1)\n",
    "                backtrack(board, i+1, j+1)\n",
    "                return \n",
    "            else:               \n",
    "                board[i][j] = str(tmp)\n",
    "                return  \n",
    "        \n",
    "\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        \n",
    "        backtrack(board, click[0], click[1])\n",
    "        return board\n",
    "         \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    GOOD_MOVE = [(-1, 0), (1, 0), (0, 1), (0, -1), (-1, 1), (-1, -1), (1, 1), (1, -1)]\n",
    "\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] in \"BX12345678\":\n",
    "            return board\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "        row, column = len(board), len(board[0])\n",
    "        # self.bfs(board, click, row, column)\n",
    "        self.dfs(board, click, row, column)\n",
    "        return board\n",
    "\n",
    "    def bfs(self, board: List[List[str]], click: List[int], row, column):\n",
    "        q = queue.Queue()\n",
    "        q.put(click)\n",
    "        while not q.empty():\n",
    "            cur_node = q.get()\n",
    "            neighbor, mine_num = self.get_nbr(*cur_node, row, column, board)\n",
    "            if mine_num:\n",
    "                board[cur_node[0]][cur_node[1]] = str(mine_num)\n",
    "            else:\n",
    "                board[cur_node[0]][cur_node[1]] = \"B\"\n",
    "                for nbr in neighbor:\n",
    "                    board[nbr[0]][nbr[1]] = \"B\"\n",
    "                    q.put(nbr)\n",
    "\n",
    "    def dfs(self, board, cur_node, r_limit, c_limit):\n",
    "        if board[cur_node[0]][cur_node[1]] in \"X12345678\":\n",
    "            return board\n",
    "        nbrs, mine_num = self.get_nbr(*cur_node, r_limit, c_limit, board)\n",
    "        if mine_num:\n",
    "            board[cur_node[0]][cur_node[1]] = str(mine_num)\n",
    "        else:\n",
    "            board[cur_node[0]][cur_node[1]] = \"B\"\n",
    "            for nbr in nbrs:\n",
    "                board[nbr[0]][nbr[1]] = \"B\"\n",
    "                self.dfs(board, nbr, r_limit, c_limit)\n",
    "\n",
    "    def get_nbr(self, row, column, r_limit, c_limit, board: List[List[str]]):\n",
    "        ret, mine_num = [], 0\n",
    "        for move in self.GOOD_MOVE:\n",
    "            nbr_r, nbr_c = row + move[0], column + move[1]\n",
    "            if 0 <= nbr_r < r_limit and 0 <= nbr_c < c_limit:\n",
    "                if board[nbr_r][nbr_c] == \"E\":\n",
    "                    ret.append((nbr_r, nbr_c))\n",
    "                if board[nbr_r][nbr_c] == \"M\":\n",
    "                    mine_num += 1\n",
    "        return ret, mine_num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        def mine(board, i, j):\n",
    "            if i<0 or i>=row or j<0 or j>=col:\n",
    "                return 0\n",
    "            num = 0\n",
    "            if i-1>=0:\n",
    "                if j-1 >=0 and board[i-1][j-1] == 'M':\n",
    "                    num += 1\n",
    "                if board[i-1][j] == 'M':\n",
    "                    num += 1\n",
    "                if j+1 < col and board[i-1][j+1]=='M':\n",
    "                    num += 1\n",
    "            if j-1 >=0 and board[i][j-1]=='M':\n",
    "                num += 1\n",
    "            if j+1 < col and board[i][j+1]=='M':\n",
    "                num += 1\n",
    "            if i+1 < row:               \n",
    "                if j-1 >=0 and board[i+1][j-1]=='M':\n",
    "                    num += 1\n",
    "                if board[i+1][j]=='M':\n",
    "                    num += 1\n",
    "                if j+1<col and board[i+1][j+1]=='M':\n",
    "                    num += 1\n",
    "            #if board[i][j] == 'M':\n",
    "             #   num += 1\n",
    "            return num\n",
    "\n",
    "        def backtrack(board, i,j):\n",
    "            if i < 0 or j >= col  or j < 0 or i  >= row or board[i][j] != 'E':\n",
    "                return \n",
    "            tmp = mine(board, i, j)\n",
    "            if tmp == 0 :\n",
    "                board[i][j] = 'B'\n",
    "                backtrack(board, i+1, j)\n",
    "                backtrack(board, i-1, j)\n",
    "                backtrack(board, i, j+1)\n",
    "                backtrack(board, i-1, j-1)               \n",
    "                backtrack(board, i-1, j+1)\n",
    "                backtrack(board, i, j-1)               \n",
    "                backtrack(board, i+1, j-1)\n",
    "                backtrack(board, i+1, j+1)\n",
    "                return \n",
    "            else:               \n",
    "                board[i][j] = str(tmp)\n",
    "                return  \n",
    "        \n",
    "\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        \n",
    "        backtrack(board, click[0], click[1])\n",
    "        return board\n",
    "         \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board, click):\n",
    "        # 将原始棋盘转换成为 recover的形式\n",
    "        # 同时计算点击下的连通图作为mask\n",
    "        # 利用mask recovery的合体来实现最终的结果\n",
    "        self.dirs = [[1,0], [-1,0], [0, 1], [0,-1],\n",
    "                [1,1], [1,-1], [-1, 1], [-1, -1]]\n",
    "        self.board = board\n",
    "        m = len(self.board)\n",
    "        n = len(self.board[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m) ]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if self.board[i][j] == 'M':\n",
    "                    dp[i][j] = -1\n",
    "                    for dir in self.dirs:\n",
    "                        if i+dir[0] >=0 and i+dir[0] < m and j+dir[1] >= 0 and j+dir[1] < n:\n",
    "                            if dp[i+dir[0]][j+dir[1]] != -1:\n",
    "                                dp[i+dir[0]][j+dir[1]]+=1   \n",
    "        \n",
    "        # 从click开始进行dfs，三种情况\n",
    "        # 1. 如果是dp 地雷，将board中的M改为X，返回\n",
    "        # 2. 如果是dp 数字，将board中的E改为数字，返回\n",
    "        # 3. 如果是dp 中的0，将board中的E改为B，然后递归的将其相邻的方块改为B\n",
    "        # loguru.logger.info(dp)\n",
    "        if dp[click[0]][click[1]] == -1:\n",
    "            self.board[click[0]][click[1]] = 'X'\n",
    "            return self.board\n",
    "        if dp[click[0]][click[1]] > 0:\n",
    "            self.board[click[0]][click[1]] = str(dp[click[0]][click[1]])\n",
    "            return self.board\n",
    "        if dp[click[0]][click[1]] == 0:\n",
    "            # 说明修改的是E\n",
    "            self.dfs(dp,click[0],click[1])\n",
    "            return self.board\n",
    "\n",
    "    def dfs(self,dp,i,j):\n",
    "        # loguru.logger.info('dfs')\n",
    "        if i<0 or i>=len(dp) or j<0 or j>=len(dp[0]):\n",
    "            # loguru.logger.info('out of range')\n",
    "            return \n",
    "        if dp[i][j] != 0:\n",
    "            # loguru.logger.info('not zero')\n",
    "            self.board[i][j] = str(dp[i][j])\n",
    "            return\n",
    "        if dp[i][j] == 0 and self.board[i][j] == 'E':\n",
    "            # loguru.logger.info('zero')\n",
    "            self.board[i][j] = 'B'\n",
    "            for dir in self.dirs:\n",
    "                self.dfs(dp,i+dir[0],j+dir[1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        i = click[0]\n",
    "        j = click[1]\n",
    "        if board[i][j] == 'M':\n",
    "            board[i][j] = 'X' \n",
    "            return board\n",
    "        else:\n",
    "            count_mine = 0\n",
    "            if i-1 >= 0:\n",
    "                if j-1 >= 0:\n",
    "                    count_mine += (board[i-1][j-1]=='M')\n",
    "                count_mine += (board[i-1][j]=='M')\n",
    "                if j+1 <= n-1:\n",
    "                    count_mine += (board[i-1][j+1]=='M')\n",
    "\n",
    "            if j-1 >= 0:\n",
    "                count_mine += (board[i][j-1]=='M')\n",
    "            count_mine += (board[i][j]=='M')\n",
    "            if j+1 <= n-1:\n",
    "                count_mine += (board[i][j+1]=='M') \n",
    "\n",
    "            if i+1 <= m-1:\n",
    "                if j-1 >= 0:\n",
    "                    count_mine += (board[i+1][j-1]=='M')\n",
    "                count_mine += (board[i+1][j]=='M')\n",
    "                if j+1 <= n-1:\n",
    "                    count_mine += (board[i+1][j+1]=='M')\n",
    "\n",
    "            if count_mine == 0:\n",
    "                board[i][j] = 'B'\n",
    "                if i-1 >= 0:\n",
    "                    if j-1 >= 0:\n",
    "                        if board[i-1][j-1] == 'E':\n",
    "                            self.updateBoard(board, [i-1, j-1])\n",
    "                    if board[i-1][j] == 'E':\n",
    "                        self.updateBoard(board, [i-1,j])\n",
    "                    if j+1 <= n-1:\n",
    "                        if board[i-1][j+1] == 'E':\n",
    "                            self.updateBoard(board, [i-1, j+1])\n",
    "\n",
    "                if j-1 >= 0:\n",
    "                    if board[i][j-1] == 'E':\n",
    "                        self.updateBoard(board, [i, j-1])\n",
    "                if j+1 <= n-1:\n",
    "                    if board[i][j+1] == 'E':\n",
    "                        self.updateBoard(board, [i, j+1]) \n",
    "\n",
    "                if i+1 <= m-1:\n",
    "                    if j-1 >= 0:\n",
    "                        if board[i+1][j-1] == 'E':\n",
    "                            self.updateBoard(board, [i+1, j-1])\n",
    "                    if board[i+1][j] == 'E':\n",
    "                        self.updateBoard(board, [i+1, j])\n",
    "                    if j+1 <= n-1:\n",
    "                        if board[i+1][j+1] == 'E':\n",
    "                            self.updateBoard(board, [i+1, j+1])\n",
    "            else:\n",
    "                board[i][j] = str(count_mine)\n",
    "            return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        def mine(board, i, j):\n",
    "            if i<0 or i>=row or j<0 or j>=col:\n",
    "                return 0\n",
    "            num = 0\n",
    "            if i-1>=0:\n",
    "                if j-1 >=0 and board[i-1][j-1] == 'M':\n",
    "                    num += 1\n",
    "                if board[i-1][j] == 'M':\n",
    "                    num += 1\n",
    "                if j+1 < col and board[i-1][j+1]=='M':\n",
    "                    num += 1\n",
    "            if j-1 >=0 and board[i][j-1]=='M':\n",
    "                num += 1\n",
    "            if j+1 < col and board[i][j+1]=='M':\n",
    "                num += 1\n",
    "            if i+1 < row:\n",
    "                \n",
    "                if j-1 >=0 and board[i+1][j-1]=='M':\n",
    "                    num += 1\n",
    "                if board[i+1][j]=='M':\n",
    "                    num += 1\n",
    "                if j+1<col and board[i+1][j+1]=='M':\n",
    "                    num += 1\n",
    "            if board[i][j] == 'M':\n",
    "                num += 1\n",
    "            return num\n",
    "\n",
    "        def backtrack(board, i,j):\n",
    "            if i < 0 or j >= col  or j < 0 or i  >= row:\n",
    "                return \n",
    "            tmp = mine(board, i, j)\n",
    "            if tmp == 0 and board[i][j] == 'E':\n",
    "                board[i][j] = 'B'\n",
    "                backtrack(board, i+1, j)\n",
    "                backtrack(board, i-1, j)\n",
    "                backtrack(board, i, j+1)\n",
    "                backtrack(board, i-1, j-1)               \n",
    "                backtrack(board, i-1, j+1)\n",
    "                backtrack(board, i, j-1)               \n",
    "                backtrack(board, i+1, j-1)\n",
    "                backtrack(board, i+1, j+1)\n",
    "                return \n",
    "            else:\n",
    "                if board[i][j] == 'E':\n",
    "                    board[i][j] = str(tmp)\n",
    "                return  \n",
    "        \n",
    "\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        \n",
    "        backtrack(board, click[0], click[1])\n",
    "        return board\n",
    "         \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def checkaround(x, y, m, n, board):\n",
    "            res = 0\n",
    "            if x+1<m and board[x+1][y] == 'M':\n",
    "                res += 1          \n",
    "            if x-1 >= 0 and board[x-1][y] == 'M':\n",
    "                res += 1\n",
    "            if y+1<n and board[x][y+1] == 'M':\n",
    "                res += 1\n",
    "            if y-1 >= 0 and board[x][y-1] == 'M':\n",
    "                res += 1\n",
    "            if x+1<m and y+1<n and board[x+1][y+1] == 'M':\n",
    "                res += 1  \n",
    "            if x+1<m and y-1>=0 and board[x+1][y-1] == 'M':\n",
    "                res += 1  \n",
    "            if x-1 >= 0 and y+1<n and board[x-1][y+1] == 'M':\n",
    "                res += 1  \n",
    "            if x-1 >= 0 and y-1>=0 and board[x-1][y-1] == 'M':\n",
    "                res += 1                                                              \n",
    "            return res\n",
    "\n",
    "        def dfs(x, y, m, n, board, ismine):\n",
    "            if x < 0 or y < 0 or x >= m or y >= n:\n",
    "                return \n",
    "            \n",
    "            if board[x][y] == 'M' and ismine:\n",
    "                board[x][y] = 'X'\n",
    "                return \n",
    "            \n",
    "            if board[x][y] == 'E':\n",
    "                ares = checkaround(x, y, m, n, board)\n",
    "                print(ares,x, y)\n",
    "                if ares != 0:\n",
    "                    board[x][y] = str(ares)\n",
    "                    #print(board)\n",
    "                    return \n",
    "                else:\n",
    "                    board[x][y] = 'B'\n",
    "                    dfs(x+1, y, m, n, board, False)\n",
    "                    dfs(x-1, y, m, n, board, False)\n",
    "                    dfs(x, y+1, m, n, board, False)\n",
    "                    dfs(x, y-1, m, n, board, False)\n",
    "\n",
    "                    dfs(x+1, y+1, m, n, board, False)\n",
    "                    dfs(x+1, y-1, m, n, board, False)\n",
    "                    dfs(x-1, y+1, m, n, board, False)\n",
    "                    dfs(x-1, y-1, m, n, board, False)\n",
    "\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        dfs(click[0],click[1], m, n, board, True)\n",
    "\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     \n",
    "    def dfs(self,board,startx,starty,m,n):\n",
    "           \n",
    "        if board[startx][starty]=='M' or board[startx][starty]=='X':\n",
    "            board[startx][starty]='X'\n",
    "            return board\n",
    "        count=0\n",
    "        for ax,ay in [(-1,0),(1,0),(0,-1),(0,1),(-1,1),(1,-1),(-1,-1),(1,1)]:     \n",
    "            nx=startx+ax\n",
    "            ny=starty+ay\n",
    "            if 0<=nx<m and 0<=ny<n and board[nx][ny]=='M':\n",
    "                count+=1\n",
    "        if count>0:\n",
    "            board[startx][starty]=str(count)\n",
    "            return board\n",
    "        board[startx][starty]='B'\n",
    "        for ax,ay in [(-1,0),(1,0),(0,-1),(0,1),(-1,1),(1,-1),(-1,-1),(1,1)]:     \n",
    "            nx=startx+ax\n",
    "            ny=starty+ay\n",
    "            if 0<=nx<m and 0<=ny<n and board[nx][ny]=='E':\n",
    "                self.dfs(board,nx,ny,m,n)\n",
    "        return board  \n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        startx=click[0]\n",
    "        starty=click[1]\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        return self.dfs(board,startx,starty,m,n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def dfs(board,click):\n",
    "            r,c=click[0],click[1]\n",
    "            if board[r][c]=='M':\n",
    "                board[r][c]='X'\n",
    "                return\n",
    "            elif board[r][c]=='E':\n",
    "                cnt=0 #炸弹数量\n",
    "                for dr,dc in directions:\n",
    "                    if 0<=r+dr<m and 0<=c+dc<n and board[r+dr][c+dc]=='M':\n",
    "                        cnt+=1\n",
    "                if cnt>0:\n",
    "                    board[r][c]=str(cnt)\n",
    "                else:\n",
    "                    board[r][c]='B'\n",
    "                    for dr,dc in directions:\n",
    "                        if 0<=r+dr<m and 0<=c+dc<n and (board[r+dr][c+dc]=='M' or board[r+dr][c+dc]=='E'):\n",
    "                            dfs(board,[r+dr,c+dc])\n",
    "            \n",
    "                    \n",
    "        m,n=len(board),len(board[0])\n",
    "        directions=[(1,0),(-1,0),(0,1),(0,-1),(1,-1),(1,1),(-1,-1),(-1,1)]\n",
    "        dfs(board,click)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        self.dx=[0,1,0,-1,1,1,-1,-1]  #水平方向偏移量\n",
    "        self.dy=[1,0,-1,0,1,-1,1,-1]  #垂直方向偏移量\n",
    "        x,y=click[0],click[1]\n",
    "        self.m,self.n=len(board),len(board[0])\n",
    "        if board[x][y]=='M':       #规则1\n",
    "            board[x][y]='X'\n",
    "        else:\n",
    "            self.dfs(board,x,y)\n",
    "        return board\n",
    "    def Count(self,board,x,y):\n",
    "        cnt=0\n",
    "        for di in range(0,8):      #求相邻地雷个数cnt\n",
    "            nx,ny=x+self.dx[di],y+self.dy[di]\n",
    "            if nx<0 or nx>=self.m or ny<0 or ny>=self.n:  #忽略超界的位置\n",
    "                continue\n",
    "            if board[nx][ny]=='M':cnt+=1\n",
    "        return cnt\n",
    "    def dfs(self,board,x,y):\n",
    "        cnt=self.Count(board,x,y)\n",
    "        if cnt==0:       #cnt=0:规则 2\n",
    "            board[x][y]='B'\n",
    "            for di in range(0,8):\n",
    "                nx,ny=x+self.dx[di],y+self.dy[di]\n",
    "                if nx<0 or nx>=self.m or ny<0 or ny>=self.n:  \n",
    "                    continue            #忽略超界的位置\n",
    "                if board[nx][ny]=='B': \n",
    "                    continue            #跳过为'B'的位置\n",
    "                self.dfs(board,nx,ny)\n",
    "        else:                        #cnt>0:规则3\n",
    "            board[x][y]=str(cnt)    #转换为数字字符\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     \n",
    "    def dfs(self,board,startx,starty,m,n):\n",
    "           \n",
    "        if board[startx][starty]=='M' :\n",
    "            board[startx][starty]='X'\n",
    "            return board\n",
    "        count=0\n",
    "        for ax,ay in [(-1,0),(1,0),(0,-1),(0,1),(-1,1),(1,-1),(-1,-1),(1,1)]:     \n",
    "            nx=startx+ax\n",
    "            ny=starty+ay\n",
    "            if 0<=nx<m and 0<=ny<n and board[nx][ny]=='M':\n",
    "                count+=1\n",
    "        if count>0:\n",
    "            board[startx][starty]=str(count)\n",
    "            return board\n",
    "        board[startx][starty]='B'\n",
    "        for ax,ay in [(-1,0),(1,0),(0,-1),(0,1),(-1,1),(1,-1),(-1,-1),(1,1)]:     \n",
    "            nx=startx+ax\n",
    "            ny=starty+ay\n",
    "            if 0<=nx<m and 0<=ny<n and board[nx][ny]=='E':\n",
    "                self.dfs(board,nx,ny,m,n)\n",
    "        return board  \n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        startx=click[0]\n",
    "        starty=click[1]\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        return self.dfs(board,startx,starty,m,n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "      # Click \"M\"\n",
    "      m,n=len(board),len(board[0])\n",
    "      r,c=click[0],click[1]\n",
    "      if r<0 or c<0 or r>=m or c>=n: return board\n",
    "      if board[r][c]==\"M\":\n",
    "        board[r][c]=\"X\"\n",
    "        return board\n",
    "      # Click \"E\"\n",
    "      elif board[r][c]==\"E\":\n",
    "        count=0\n",
    "        for i in range(8):\n",
    "          rr=r+self.directions[i][0]\n",
    "          cc=c+self.directions[i][1]\n",
    "          if rr>=0 and rr<m and cc>=0 and cc<n and board[rr][cc]==\"M\":\n",
    "            count+=1\n",
    "        if count>0:\n",
    "          board[r][c]=str(count)\n",
    "          return board\n",
    "        else:\n",
    "          board[r][c]=\"B\"\n",
    "          for i in range(8):\n",
    "            rr=r+self.directions[i][0]\n",
    "            cc=c+self.directions[i][1]\n",
    "            self.updateBoard(board,[rr,cc])\n",
    "          return board\n",
    "      else:\n",
    "        return board\n",
    "\n",
    "    directions=[[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        # print (board)\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        r, c = click\n",
    "        if (board[r][c] == 'M'):\n",
    "            board[r][c] = 'X'\n",
    "            return board\n",
    "\n",
    "        if (board[r][c] != 'E'):\n",
    "            return board\n",
    "\n",
    "        # print (board, r, c, board[r][c])\n",
    "        cnt = 0\n",
    "        for i, j in [[r-1, c-1],[r-1, c],[r-1, c+1],[r, c-1],[r, c+1],[r+1, c-1],[r+1, c],[r+1, c+1]]:\n",
    "            if (i >=0 and j>=0 and i<=m-1 and j<=n-1 and board[i][j] == 'M'):\n",
    "                # print (i,j)\n",
    "                cnt += 1\n",
    "\n",
    "        if (cnt > 0):\n",
    "            # print (cnt)\n",
    "            board[r][c] = str(cnt)\n",
    "            return board\n",
    "\n",
    "        board[r][c] = 'B'\n",
    "        if (r>=1 and c>=1):\n",
    "            board = self.updateBoard(board, [r-1, c-1])\n",
    "        \n",
    "        if (r>=1 and c<=n-2):\n",
    "            board = self.updateBoard(board, [r-1, c+1])\n",
    "\n",
    "        if (r >= 1):\n",
    "            board = self.updateBoard(board, [r-1, c])\n",
    "\n",
    "        if (c >= 1):\n",
    "            board = self.updateBoard(board, [r, c-1])\n",
    "\n",
    "        if (c <= n-2):\n",
    "            board = self.updateBoard(board, [r, c+1])\n",
    "\n",
    "        if (r<=m-2 and c>=1):\n",
    "            board = self.updateBoard(board, [r+1, c-1])\n",
    "        \n",
    "        if (r<=m-2 and c<=n-2):\n",
    "            board = self.updateBoard(board, [r+1, c+1])\n",
    "\n",
    "        if (r <= m-2):\n",
    "            board = self.updateBoard(board, [r+1, c])\n",
    "\n",
    "        return board\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        x,y=click\n",
    "        if board[x][y].isdigit() or board[x][y]=='B':\n",
    "            return board\n",
    "        if board[click[0]][click[1]]=='M':\n",
    "            board[click[0]][click[1]]='X'\n",
    "        elif board[click[0]][click[1]]=='E':\n",
    "            count=0\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if 0<=x-1+i<len(board) and 0<=y-1+j<len(board[0]):\n",
    "                        if board[x-1+i][y-1+j]=='M':\n",
    "                            count+=1\n",
    "            if count==0:\n",
    "                board[x][y]='B'\n",
    "                for i in range(3):\n",
    "                    for j in range(3):\n",
    "                        if 0<=x-1+i<len(board) and 0<=y-1+j<len(board[0]):\n",
    "                            self.updateBoard(board,[x-1+i,y-1+j])\n",
    "            else:\n",
    "                board[x][y]=str(count)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        \n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        directions = [(-1,0),(0,-1),(0,1),(1,0),(1,1),(1,-1),(-1,1),(-1,-1)]\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            visited[i][j]=1\n",
    "\n",
    "            if board[i][j]=='M':\n",
    "                board[i][j]='X'\n",
    "                return\n",
    "            elif board[i][j]=='E':\n",
    "\n",
    "                neighbor = 0\n",
    "                visited[i][j]=1\n",
    "                for d_i,d_j in directions:\n",
    "                    new_i,new_j = i+d_i,j+d_j\n",
    "                    if 0<=new_i<m and 0<=new_j<n and board[new_i][new_j]=='M':\n",
    "                        neighbor+=1\n",
    "                if neighbor>0:\n",
    "                    board[i][j]=str(neighbor)\n",
    "                else:\n",
    "                    board[i][j]='B'\n",
    "                    visited[i][j]=1\n",
    "                    for d_i,d_j in directions:\n",
    "                        new_i,new_j = i+d_i,j+d_j\n",
    "                        if 0<=new_i<m and 0<=new_j<n and not visited[new_i][new_j]:\n",
    "                            dfs(new_i,new_j)\n",
    "            \n",
    "                \n",
    "                \n",
    "                \n",
    "         \n",
    "\n",
    "            pass\n",
    "\n",
    "        dfs(click[0],click[1])\n",
    "\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        col = click[1]\n",
    "        row = click[0]\n",
    "        res = [board]\n",
    "        if board[row][col] == \"X\" or board[row][col] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "        elif board[click[0]][click[1]] == \"E\":\n",
    "            used = []\n",
    "            self.getboard(board,row,col,used,m,n,res)\n",
    "        return res[0]\n",
    "    def getboard(self,board,row,col,used,m,n,res):\n",
    "        Sum = 0\n",
    "        if row - 1 >= 0:\n",
    "            if board[row-1][col] == \"X\" or board[row-1][col] == \"M\":\n",
    "                Sum += 1\n",
    "            if col - 1 >= 0:\n",
    "                if board[row-1][col-1] == \"X\" or board[row-1][col-1] == \"M\":\n",
    "                    Sum += 1\n",
    "            if col + 1 < n:\n",
    "                if board[row-1][col+1] == \"X\" or board[row-1][col+1] == \"M\":\n",
    "                    Sum += 1\n",
    "        if row + 1 < m:\n",
    "            if board[row+1][col] == \"X\" or board[row+1][col] == \"M\":\n",
    "                Sum += 1\n",
    "            if col - 1 >= 0:\n",
    "                if board[row+1][col-1] == \"X\" or board[row+1][col-1] == \"M\":\n",
    "                    Sum += 1\n",
    "            if col + 1 < n:\n",
    "                if board[row+1][col+1] == \"X\" or board[row+1][col+1] == \"M\":\n",
    "                    Sum += 1\n",
    "        if col - 1 >= 0:\n",
    "            if board[row][col-1] == \"X\" or board[row][col-1] == \"M\":\n",
    "                Sum += 1\n",
    "        if col + 1 < n:\n",
    "            if board[row][col+1] == \"X\" or board[row][col+1] == \"M\":\n",
    "                Sum += 1\n",
    "        used.append((row,col))\n",
    "        if Sum == 0:\n",
    "            board[row][col] = \"B\"\n",
    "            res[0][row][col] = \"B\" \n",
    "            if row - 1 >= 0:\n",
    "                if (row-1,col) not in used:\n",
    "                    self.getboard(board,row-1,col,used,m,n,res)\n",
    "            if col - 1 >= 0:\n",
    "                if (row,col-1) not in used:\n",
    "                    self.getboard(board,row,col-1,used,m,n,res)\n",
    "            if row + 1 < m:\n",
    "                if (row+1,col) not in used:\n",
    "                    self.getboard(board,row+1,col,used,m,n,res)\n",
    "            if col + 1 < n:\n",
    "                if (row,col+1) not in used:\n",
    "                    self.getboard(board,row,col+1,used,m,n,res)\n",
    "            if row - 1 >= 0:\n",
    "                if col - 1 >= 0:\n",
    "                    if (row-1,col-1) not in used:\n",
    "                        self.getboard(board,row-1,col-1,used,m,n,res)\n",
    "                if col + 1 < n:\n",
    "                    if (row-1,col+1) not in used:\n",
    "                        self.getboard(board,row-1,col+1,used,m,n,res)\n",
    "            if row + 1 < m:\n",
    "                if col - 1 >= 0:\n",
    "                    if (row+1,col-1) not in used:\n",
    "                        self.getboard(board,row+1,col-1,used,m,n,res)\n",
    "                if col + 1 < n :\n",
    "                    if (row+1,col+1) not in used:\n",
    "                        self.getboard(board,row+1,col+1,used,m,n,res)\n",
    "        else:\n",
    "            board[row][col] = str(Sum)\n",
    "            res[0][row][col] = str(Sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        x,y = click\n",
    "        m,n=len(board),len(board[0])\n",
    "        bd=[[0 for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='M':\n",
    "                    for a in [-1,0,1]:\n",
    "                        for b in [-1,0,1]:\n",
    "                            if a==0 and b==0:\n",
    "                                continue\n",
    "                            ni,nj=i+a,j+b\n",
    "                            if 0<=ni<m and 0<=nj<n:\n",
    "                                bd[ni][nj]+=1\n",
    "        print(bd)\n",
    "        if board[x][y]=='M':\n",
    "            board[x][y]='X'\n",
    "            return board\n",
    "        if bd[x][y]!=0:\n",
    "            board[x][y]=str(bd[x][y])\n",
    "            return board\n",
    "        rds=[(0,1),(1,0),(-1,0),(0,-1),(1,-1),(1,1),(-1,1),(-1,-1)]\n",
    "        visited=set()\n",
    "        def dfs(i,j):\n",
    "            visited.add((i,j))\n",
    "            if bd[i][j]!=0:\n",
    "                board[i][j]=str(bd[i][j])\n",
    "                return\n",
    "            else:\n",
    "                board[i][j]='B'\n",
    "                for x,y in rds:\n",
    "                    nx,ny=x+i,y+j\n",
    "                    if 0<=nx<m and 0<=ny<n and (nx,ny) not in visited:\n",
    "                        dfs(nx,ny)\n",
    "\n",
    "        dfs(x,y)\n",
    "        return board\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            cnt = 0\n",
    "            visited[i][j] = 1\n",
    "            if i > 0 and board[i - 1][j] == 'M': cnt += 1\n",
    "            if j > 0 and board[i][j - 1] == 'M': cnt += 1\n",
    "            if i < len(board) - 1 and board[i + 1][j] == 'M': cnt += 1\n",
    "            if j < len(board[0]) - 1 and board[i][j + 1] == 'M': cnt += 1\n",
    "            if i > 0 and j > 0 and board[i - 1][j - 1] == 'M': cnt += 1\n",
    "            if i > 0 and j < len(board[0]) - 1 and board[i - 1][j + 1] == 'M': cnt += 1\n",
    "            if i < len(board) - 1 and j > 0 and board[i + 1][j - 1] == 'M': cnt += 1\n",
    "            if i < len(board) - 1 and j < len(board[0]) - 1 and board[i + 1][j + 1] == 'M': cnt += 1\n",
    "            if cnt > 0: \n",
    "                board[i][j] = str(cnt)\n",
    "                return\n",
    "            board[i][j] = 'B'\n",
    "            if i > 0:\n",
    "                if board[i - 1][j] == 'E' and visited[i - 1][j] == 0: dfs(i - 1, j)\n",
    "            if j > 0:\n",
    "                if board[i][j - 1] == 'E' and visited[i][j - 1] == 0: dfs(i, j - 1)\n",
    "            if i < len(board) - 1:\n",
    "                if board[i + 1][j] == 'E' and visited[i + 1][j] == 0: dfs(i + 1, j)\n",
    "            if j < len(board[0]) - 1:\n",
    "                if board[i][j + 1] == 'E' and visited[i][j + 1] == 0: dfs(i, j + 1)\n",
    "            if i > 0 and j > 0:\n",
    "                if board[i - 1][j - 1] == 'E' and visited[i - 1][j - 1] == 0: dfs(i - 1, j - 1)\n",
    "            if i > 0 and j < len(board[0]) - 1:\n",
    "                if board[i - 1][j + 1] == 'E' and visited[i - 1][j + 1] == 0: dfs(i - 1, j + 1)\n",
    "            if i < len(board) - 1 and j > 0:\n",
    "                if board[i + 1][j - 1] == 'E' and visited[i + 1][j - 1] == 0: dfs(i + 1, j - 1)\n",
    "            if i < len(board) - 1 and j < len(board[0]) - 1:\n",
    "                if board[i + 1][j + 1] == 'E' and visited[i + 1][j + 1] == 0: dfs(i + 1, j + 1)\n",
    "\n",
    "        dfs(click[0], click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        dirs = [[0, -1], [0, 1], [-1, 0], [1, 0], [-1, 1], [1, -1], [-1, -1], [1, 1]]\n",
    "        def reveal(i: int, j: int):\n",
    "            if board[i][j] == 'B':\n",
    "                return\n",
    "            if board[i][j] == 'M':\n",
    "                board[i][j] = 'X'\n",
    "                return\n",
    "            numMines = 0\n",
    "            for x, y in dirs:\n",
    "                newI, newJ = i + x, j + y\n",
    "                if newI < 0 or newI >= len(board) or newJ < 0 or newJ >= len(board[newI]):\n",
    "                    continue\n",
    "                if board[newI][newJ] == 'M':\n",
    "                    numMines += 1\n",
    "            if numMines > 0:\n",
    "                board[i][j] = str(numMines)\n",
    "                return\n",
    "            board[i][j] = 'B'\n",
    "            for x, y in dirs:\n",
    "                newI, newJ = i + x, j + y\n",
    "                if newI < 0 or newI >= len(board) or newJ < 0 or newJ >= len(board[newI]):\n",
    "                    continue\n",
    "                if board[newI][newJ] == 'E':\n",
    "                    reveal(newI, newJ)\n",
    "        \n",
    "        reveal(click[0], click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def dfs(x, y):\n",
    "            bomb = count(x, y)\n",
    "            if bomb:\n",
    "                board[x][y] = str(bomb)\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for dx, dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == 'E':\n",
    "                        dfs(nx, ny)\n",
    "        \n",
    "        def count(x, y):\n",
    "            num = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == 'M':\n",
    "                    num += 1\n",
    "            return num\n",
    "        \n",
    "        x, y = click[0], click[1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return board\n",
    "        row, col = len(board), len(board[0])\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]\n",
    "        dfs(x, y)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        #初始坐标\n",
    "        x,y=click[0],click[1]\n",
    "        max_r,max_c=len(board)-1,len(board[0])-1\n",
    "        def method(board,x,y):\n",
    "            cur_block=board[x][y]\n",
    "            if cur_block=='M':\n",
    "                board[x][y]='X'\n",
    "                return True\n",
    "            elif cur_block=='E':\n",
    "                con=[]\n",
    "                #上\n",
    "                if x-1>=0:\n",
    "                    con.append((x-1,y))\n",
    "                #右上\n",
    "                if x-1>=0 and y+1<=max_c:\n",
    "                    con.append((x-1,y+1))\n",
    "                if y+1<=max_c:\n",
    "                    con.append((x,y+1))\n",
    "                #右下\n",
    "                if x+1<=max_r and y+1<=max_c:\n",
    "                    con.append((x+1,y+1))\n",
    "                #下\n",
    "                if x+1<=max_r:\n",
    "                    con.append((x+1,y))\n",
    "                #左下\n",
    "                if x+1<=max_r and y-1>=0:\n",
    "                    con.append((x+1,y-1))\n",
    "                #左\n",
    "                if y-1>=0:\n",
    "                    con.append((x,y-1))\n",
    "                #左上\n",
    "                if x-1>=0 and y-1>=0:\n",
    "                    con.append((x-1,y-1))\n",
    "                thunder_count=0 #当前方块周围雷的数量\n",
    "                for new_x,new_y in con:\n",
    "                    if board[new_x][new_y]=='M':\n",
    "                        thunder_count+=1\n",
    "                if thunder_count==0:\n",
    "                    board[x][y]='B'\n",
    "                    while con:\n",
    "                        next_coordinate=con.pop(0)\n",
    "                        res=method(board,next_coordinate[0],next_coordinate[1])\n",
    "                        if res:\n",
    "                            return True\n",
    "                    return False\n",
    "                else:\n",
    "                    board[x][y]=str(thunder_count)\n",
    "                    return False\n",
    "            return False\n",
    "        method(board,x,y)\n",
    "        return board\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        # dfs\n",
    "        def dfs(x, y):\n",
    "            # board[x][y] == 'E'\n",
    "            cnt = check(x, y)\n",
    "            if not cnt:\n",
    "                board[x][y] = 'B'\n",
    "                for dx, dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == 'E':\n",
    "                        dfs(nx, ny)\n",
    "            else:\n",
    "                board[x][y] = str(cnt)\n",
    "\n",
    "        def check(x, y):\n",
    "            cnt = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == 'M':\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "\n",
    "        x, y = click[0], click[1]\n",
    "        if board[x][y] == 'M':\n",
    "            board[x][y] = 'X'\n",
    "            return board\n",
    "        row, col = len(board), len(board[0])\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]]\n",
    "        dfs(x, y)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def border_mine(v):\n",
    "            x, y = v[0], v[1]\n",
    "            mine_c = 0\n",
    "            for dx, dy in Direct:\n",
    "                next_x, next_y = x + dx, y + dy\n",
    "                if 0 <= next_x < m and 0 <= next_y < n and board[next_x][next_y] == \"M\":\n",
    "                    mine_c += 1\n",
    "            return (True, mine_c) if mine_c > 0 else (False, 0)\n",
    "\n",
    "        def dfs(v):\n",
    "            x, y = v[0], v[1]\n",
    "            visited[x][y] = True\n",
    "            if board[x][y] == \"M\":\n",
    "                board[x][y] = \"X\"\n",
    "                return\n",
    "            elif board[x][y] == \"E\":\n",
    "                have_mine, mine_c = border_mine(v)\n",
    "                if have_mine:\n",
    "                    board[x][y] = str(mine_c)\n",
    "                    return\n",
    "                else:\n",
    "                    board[x][y] = \"B\"\n",
    "                    for dx, dy in Direct:\n",
    "                        next_x, next_y = x + dx, y + dy\n",
    "                        if 0 <= next_x < m and 0 <= next_y < n and visited[next_x][next_y] == False:\n",
    "                            w = (next_x, next_y)\n",
    "                            dfs(w)\n",
    "            else:\n",
    "                return\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        Direct = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (1, -1), (-1, 1), (1, 1)]\n",
    "        dfs((click[0], click[1]))\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        # 初始坐标\n",
    "        x, y = click[0], click[1]\n",
    "        max_r, max_c = len(board)-1, len(board[0])-1\n",
    "        def method(board, x, y):\n",
    "            cur_block = board[x][y]\n",
    "            if cur_block == 'M':\n",
    "                board[x][y] = 'X'\n",
    "                return True\n",
    "            elif cur_block == 'E':  # 代表一个 未挖出的 空方块\n",
    "                con = []\n",
    "                # 上\n",
    "                if x-1 >= 0:\n",
    "                    con.append((x-1, y))\n",
    "                # 右上\n",
    "                if x-1 >= 0 and y+1 <= max_c:\n",
    "                    con.append((x-1, y+1))\n",
    "                # 右\n",
    "                if y+1 <= max_c:\n",
    "                    con.append((x, y+1))\n",
    "                # 右下\n",
    "                if x+1 <= max_r and y+1 <= max_c:\n",
    "                    con.append((x+1, y+1))\n",
    "                # 下\n",
    "                if x+1 <= max_r:\n",
    "                    con.append((x+1, y))\n",
    "                # 左下\n",
    "                if x+1 <= max_r and y-1 >= 0:\n",
    "                    con.append((x+1, y-1))\n",
    "                # 左\n",
    "                if y-1 >= 0:\n",
    "                    con.append((x, y-1))\n",
    "                # 左上\n",
    "                if x-1 >= 0 and y-1 >= 0:\n",
    "                    con.append((x-1, y-1))\n",
    "                thunder_count = 0    # 当前方块周围雷的数量\n",
    "                for new_x, new_y in con:\n",
    "                    if board[new_x][new_y] == 'M':\n",
    "                        thunder_count += 1\n",
    "                if thunder_count == 0:   # 当前方块周围雷的数量为0，则继续排雷\n",
    "                    board[x][y] = 'B'\n",
    "                    while con:\n",
    "                        next_coordinate = con.pop(0)\n",
    "                        res = method(board, next_coordinate[0], next_coordinate[1])\n",
    "                        if res:\n",
    "                            return True\n",
    "\n",
    "                    return False\n",
    "                else:\n",
    "                    board[x][y] = str(thunder_count)\n",
    "                    return False\n",
    "\n",
    "            return False\n",
    "        method(board, x, y)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m=click[0]\n",
    "        n=click[1]\n",
    "        dot=board[m][n]\n",
    "        if dot==\"M\":\n",
    "            board[m][n]=\"X\"\n",
    "            return board\n",
    "        p=len(board)\n",
    "        q=len(board[0])\n",
    "        direction = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1))\n",
    "        def check(i, j):\n",
    "                cnt = 0\n",
    "                for x,y in direction:\n",
    "                    x, y = x + i, y + j\n",
    "                    if 0 <= x < p and 0 <= y < q and board[x][y]=='M':\n",
    "                        cnt += 1\n",
    "                return cnt    \n",
    "\n",
    "        def dfs(i, j):\n",
    "            cnt = check(i, j)\n",
    "            if cnt==0:\n",
    "                board[i][j] = 'B'\n",
    "                for x, y in direction:\n",
    "                    x, y = x + i, y + j\n",
    "                    if  0 <= x < p and 0 <= y < q and board[x][y]=='E': \n",
    "                        dfs(x, y)\n",
    "            else: \n",
    "                board[i][j] = str(cnt)\n",
    "\n",
    "        dfs(m,n)\n",
    "        return board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        \n",
    "            direction = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1))\n",
    "            if board[click[0]][click[1]] == 'M':\n",
    "                board[click[0]][click[1]] = 'X'\n",
    "                return board\n",
    "            self.m,self.n = len(board), len(board[0])\n",
    "            def check(i, j):\n",
    "                cnt = 0\n",
    "                for x,y in direction:\n",
    "                    x, y = x + i, y + j\n",
    "                    if 0 <= x < self.m and 0 <= y < self.n and board[x][y]=='M':\n",
    "                        cnt += 1\n",
    "                return cnt    \n",
    "            def dfs(i, j):\n",
    "                cnt = check(i, j)\n",
    "                if not cnt:\n",
    "                    board[i][j] = 'B'\n",
    "                    for x, y in direction:\n",
    "                        x, y = x + i, y + j\n",
    "                        if  0 <= x < self.m and 0 <= y < self.n and board[x][y]=='E': dfs(x, y)\n",
    "                else: board[i][j] = str(cnt)\n",
    "            dfs(click[0],click[1])\n",
    "            return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        def check_grid(grid: list):\n",
    "            bomb_count = 0\n",
    "            for i in grid:\n",
    "                if board[i[0]][i[1]] == 'M':\n",
    "                    bomb_count += 1\n",
    "            \n",
    "            return bomb_count\n",
    "\n",
    "        def count_bomb(i, j):\n",
    "            bomb_count = 0\n",
    "            if i > 0:\n",
    "                b_count = check_grid([[i - 1, j]])\n",
    "                bomb_count += b_count\n",
    "                if j > 0:\n",
    "                    b_count = check_grid([[i - 1, j - 1]])\n",
    "                    bomb_count += b_count\n",
    "                if j < n-1:\n",
    "                    b_count = check_grid([[i - 1, j + 1]])\n",
    "                    bomb_count += b_count\n",
    "            if i < m - 1:\n",
    "                b_count = check_grid([[i + 1, j]])\n",
    "                bomb_count += b_count\n",
    "                if j > 0:\n",
    "                    b_count = check_grid([[i + 1, j - 1]])\n",
    "                    bomb_count += b_count\n",
    "                if j < n-1:\n",
    "                    b_count = check_grid([[i + 1, j + 1]])\n",
    "                    bomb_count += b_count\n",
    "            if j > 0:\n",
    "                b_count = check_grid([[i, j- 1]])\n",
    "                bomb_count += b_count\n",
    "            if j < n-1:\n",
    "                b_count = check_grid([[i, j + 1]])\n",
    "                bomb_count += b_count\n",
    "            return bomb_count\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if board[i][j] != 'E':\n",
    "                return\n",
    "\n",
    "            bomb_count = count_bomb(i, j)\n",
    "            if bomb_count == 0:\n",
    "                board[i][j] = 'B'\n",
    "                if i > 0:\n",
    "                    dfs(i - 1, j)\n",
    "                    if j > 0:\n",
    "                        dfs(i - 1, j - 1)\n",
    "                        dfs(i, j- 1)\n",
    "                    if j < n-1:\n",
    "                        dfs(i - 1, j + 1)\n",
    "                        dfs(i, j + 1)\n",
    "                if i < m - 1:\n",
    "                    dfs(i + 1, j)\n",
    "                    if j > 0:\n",
    "                        dfs(i + 1, j - 1)\n",
    "                        dfs(i, j- 1)\n",
    "                    if j < n-1:\n",
    "                        dfs(i + 1, j + 1)\n",
    "                        dfs(i, j + 1)\n",
    "            else:\n",
    "                board[i][j] = f\"{bomb_count}\"\n",
    "\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        elif board[click[0]][click[1]] == 'E':\n",
    "            dfs(click[0], click[1])\n",
    "        \n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        direction = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1))\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        self.m, self.n = len(board), len(board[0])\n",
    "        def check(i, j):\n",
    "            cnt = 0\n",
    "            for x, y in direction:\n",
    "                x, y = x + i, y + j\n",
    "                if 0 <= x < self.m and 0 <= y < self.n and board[x][y]== 'M':\n",
    "                    cnt += 1\n",
    "            return cnt    \n",
    "        def dfs(i, j):\n",
    "            cnt = check(i, j)\n",
    "            if cnt == 0:\n",
    "                board[i][j] = 'B'\n",
    "                for x, y in direction:\n",
    "                    x, y = x + i, y + j\n",
    "                    if  0 <= x < self.m and 0 <= y < self.n and board[x][y] == 'E': dfs(x, y)\n",
    "            else: board[i][j] = str(cnt)\n",
    "        dfs(click[0], click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        def check_grid(grid: list):\n",
    "            bomb_count = 0\n",
    "            for i in grid:\n",
    "                if board[i[0]][i[1]] == 'M':\n",
    "                    bomb_count += 1\n",
    "            \n",
    "            return bomb_count\n",
    "\n",
    "        def count_bomb(i, j):\n",
    "            bomb_count = 0\n",
    "            if i > 0:\n",
    "                b_count = check_grid([[i - 1, j]])\n",
    "                bomb_count += b_count\n",
    "                if j > 0:\n",
    "                    b_count = check_grid([[i - 1, j - 1]])\n",
    "                    bomb_count += b_count\n",
    "                if j < n-1:\n",
    "                    b_count = check_grid([[i - 1, j + 1]])\n",
    "                    bomb_count += b_count\n",
    "            if i < m - 1:\n",
    "                b_count = check_grid([[i + 1, j]])\n",
    "                bomb_count += b_count\n",
    "                if j > 0:\n",
    "                    b_count = check_grid([[i + 1, j - 1]])\n",
    "                    bomb_count += b_count\n",
    "                if j < n-1:\n",
    "                    b_count = check_grid([[i + 1, j + 1]])\n",
    "                    bomb_count += b_count\n",
    "            if j > 0:\n",
    "                b_count = check_grid([[i, j- 1]])\n",
    "                bomb_count += b_count\n",
    "            if j < n-1:\n",
    "                b_count = check_grid([[i, j + 1]])\n",
    "                bomb_count += b_count\n",
    "            return bomb_count\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if board[i][j] != 'E':\n",
    "                return\n",
    "\n",
    "            bomb_count = count_bomb(i, j)\n",
    "            if bomb_count == 0:\n",
    "                board[i][j] = 'B'\n",
    "                if i > 0:\n",
    "                    dfs(i - 1, j)\n",
    "                    if j > 0:\n",
    "                        dfs(i - 1, j - 1)\n",
    "                        dfs(i, j- 1)\n",
    "                    if j < n-1:\n",
    "                        dfs(i - 1, j + 1)\n",
    "                        dfs(i, j + 1)\n",
    "                if i < m - 1:\n",
    "                    dfs(i + 1, j)\n",
    "                    if j > 0:\n",
    "                        dfs(i + 1, j - 1)\n",
    "                        dfs(i, j- 1)\n",
    "                    if j < n-1:\n",
    "                        dfs(i + 1, j + 1)\n",
    "                        dfs(i, j + 1)\n",
    "            else:\n",
    "                board[i][j] = f\"{bomb_count}\"\n",
    "\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        elif board[click[0]][click[1]] == 'E':\n",
    "            dfs(click[0], click[1])\n",
    "        \n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        \n",
    "        if board[click[0]][click[1]]==\"M\":\n",
    "           board[click[0]][click[1]]=\"X\"\n",
    "           return board\n",
    "        direction = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1),         (-1, -1), (1, -1))\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        \n",
    "        def count(i,j):\n",
    "            cnt=0\n",
    "            for x,y in direction:\n",
    "                x,y=i+x,j+y\n",
    "                if 0<=x<m and 0<=y<n and board[x][y]==\"M\":\n",
    "                    cnt+=1\n",
    "            return cnt\n",
    "        def update(i,j):\n",
    "            cnt=count(i,j)\n",
    "            if cnt==0:\n",
    "                board[i][j]=\"B\"\n",
    "                for x,y in direction:\n",
    "                    x,y=i+x,j+y\n",
    "                    if 0<=x<m and 0<=y<n and board[x][y]==\"E\":\n",
    "                        update(x,y)\n",
    "            else:\n",
    "                board[i][j]=str(cnt)\n",
    "\n",
    "        update(click[0],click[1])\n",
    "        return board\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        #show语句,不方便在board上更改，可以考虑vis数组\n",
    "        m,n=len(board),len(board[0])\n",
    "        def dfs(i:int,j:int)->None:\n",
    "            cnt=0\n",
    "            #这是对第一次点击做判断\n",
    "            if board[i][j]!='E':\n",
    "                board[i][j]='X'\n",
    "                return\n",
    "            for x in range(i-1,i+2):\n",
    "                for y in range(j-1,j+2):\n",
    "                    if 0<=x<m and 0<=y<n and board[x][y]=='M':\n",
    "                        cnt+=1\n",
    "            board[i][j]=str(cnt) if cnt else 'B'\n",
    "            if cnt==0:\n",
    "                for x in range(i-1,i+2):\n",
    "                    for y in range(j-1,j+2):\n",
    "                        if 0<=x<m and 0<=y<n and board[x][y]=='E':\n",
    "                            dfs(x,y)\n",
    "        dfs(click[0],click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        '''\n",
    "        [['E', 'E', 'E', 'E', 'E'],\n",
    "        ['E', 'E', 'M', 'E', 'E'],\n",
    "        ['B', 'B', 'E', 'E', 'E'],\n",
    "        ['B', 'E', 'E', 'E', 'E']]\n",
    "        '''\n",
    "        dic=[[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] \n",
    "        def search_around(x,y):\n",
    "            count=0\n",
    "            for i,j in dic:\n",
    "                if 0<=x+i<=n-1 and 0<=y+j<=m-1:\n",
    "                    if board[x+i][y+j]=='M':\n",
    "                        count+=1\n",
    "            return count\n",
    "        def dfs(x,y): \n",
    "            if x<0 or x>n-1 or y<0 or y>m-1:\n",
    "                return \n",
    "            if board[x][y]!='E': \n",
    "                return \n",
    "            count=search_around(x,y) \n",
    "            if count!=0:\n",
    "                board[x][y]=str(count)\n",
    "                return \n",
    "            else:\n",
    "                board[x][y]='B'\n",
    "                for i,j in dic:\n",
    "                    dfs(x+i,y+j)\n",
    "        n=len(board)\n",
    "        m=len(board[0])\n",
    "        if board[click[0]][click[1]]=='M': \n",
    "            board[click[0]][click[1]]='X'\n",
    "            return board\n",
    "        else:\n",
    "            dfs(click[0],click[1])\n",
    "            return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        _next = {-1, 0, 1}\n",
    "        _x = click[0]\n",
    "        _y = click[1]\n",
    "\n",
    "        def count_bomb(i, j):\n",
    "            bomb_count = 0\n",
    "\n",
    "            for x in _next:\n",
    "                for y in _next:\n",
    "                    if x != 0 or y != 0:\n",
    "                        if 0 <= i + x <= m-1 and 0 <= j + y <= n-1:\n",
    "                            if board[i + x][j + y] == 'M':\n",
    "                                bomb_count += 1\n",
    "            \n",
    "            return bomb_count\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if board[i][j] != 'E':\n",
    "                return\n",
    "            \n",
    "            bomb_count = count_bomb(i, j)\n",
    "            if bomb_count != 0:\n",
    "                board[i][j] = f\"{bomb_count}\"\n",
    "            else:\n",
    "                board[i][j] = 'B'\n",
    "                for x in _next:\n",
    "                    for y in _next:\n",
    "                        if x != 0 or y != 0:\n",
    "                            if 0 <= i + x <= m - 1 and 0 <= j + y <= n - 1:\n",
    "                                print(\"ok\", i + x, j + y)\n",
    "                                dfs(i + x, j + y)\n",
    "        \n",
    "        if board[_x][_y] == 'M':\n",
    "            board[_x][_y] = 'X'\n",
    "            return board\n",
    "        elif board[_x][_y] == 'E':\n",
    "            dfs(_x, _y)\n",
    "        \n",
    "        return board\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        directions = [(1, 1), (1, 0), (-1, 0), (-1, -1), (0, -1), (0, 1), (1, -1), (-1, 1)]\n",
    "\n",
    "        def _click(x, y):     \n",
    "            mine_count = 0\n",
    "            to_be_visited = set()\n",
    "            for i, j in directions:\n",
    "                _x = x + i\n",
    "                _y = y + j\n",
    "                if 0 <= _x < m and 0 <= _y < n:\n",
    "                    if board[_x][_y] == 'M':\n",
    "                        mine_count += 1\n",
    "                    elif board[_x][_y] == 'E':\n",
    "                        to_be_visited.add((_x, _y))\n",
    "            if mine_count > 0:\n",
    "                board[x][y] = str(mine_count)\n",
    "            else:\n",
    "                board[x][y] = 'B'\n",
    "                for _x, _y in to_be_visited:\n",
    "                    _click(_x, _y)\n",
    "\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "        elif board[click[0]][click[1]] == 'E':\n",
    "            _click(click[0], click[1])\n",
    "    \n",
    "        return board\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        dir = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]\n",
    "        def sum(row, col):\n",
    "            val = 0\n",
    "            for i in range(0, len(dir)):\n",
    "                val += calc(row + dir[i][0], col + dir[i][1])\n",
    "            return val\n",
    "        def calc(row, col):\n",
    "            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):\n",
    "                return 0\n",
    "            else:\n",
    "                if board[row][col] == 'M':\n",
    "                    return 1\n",
    "                return 0\n",
    "        def dfs(row, col):\n",
    "            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != 'E':\n",
    "                return\n",
    "            val = sum(row, col)\n",
    "            if val == 0:\n",
    "                board[row][col] = 'B'\n",
    "                for i in range(0, len(dir)):\n",
    "                    dfs(row + dir[i][0], col + dir[i][1])\n",
    "            else:\n",
    "                board[row][col] = str(val)\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "        elif board[click[0]][click[1]] == 'E':\n",
    "            val = sum(click[0], click[1])\n",
    "            if val == 0:\n",
    "                dfs(click[0], click[1])\n",
    "            else:\n",
    "                board[click[0]][click[1]] = str(val)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        def dfs(row: int, col: int):\n",
    "            vis.add((row, col))\n",
    "            directions = (\n",
    "                (-1, -1),\n",
    "                (-1, 0),\n",
    "                (-1, 1),\n",
    "                (0, -1),\n",
    "                (0, 1),\n",
    "                (1, -1),\n",
    "                (1, 0),\n",
    "                (1, 1),\n",
    "            )\n",
    "            mine = 0\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = row + dx, col + dy\n",
    "                if 0 <= nx < M and 0 <= ny < N:\n",
    "                    if board[nx][ny] == 'M':\n",
    "                        mine += 1\n",
    "            if mine != 0:\n",
    "                board[row][col] = str(mine)\n",
    "            else:\n",
    "                board[row][col] = \"B\"\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = row + dx, col + dy\n",
    "                    if 0 <= nx < M and 0 <= ny < N and (nx, ny) not in vis:\n",
    "                        dfs(nx, ny)\n",
    "            \n",
    "        M, N = len(board), len(board[0])\n",
    "        row, col = click\n",
    "\n",
    "        match board[row][col]:\n",
    "            case \"M\":\n",
    "                board[row][col] = \"X\"\n",
    "            case \"E\":\n",
    "                vis = set()\n",
    "                dfs(row, col)\n",
    "        \n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "            return board\n",
    "        def check(x,y):\n",
    "            count = 0\n",
    "            for m,n in ((x+1,y),(x-1,y),(x-1,y-1),(x+1,y-1),(x-1,y+1),(x+1,y+1),(x,y-1),(x,y+1)):\n",
    "                if 0 <= m < len(board) and 0 <= n < len(board[0]) and board[m][n] == 'M':\n",
    "                    count += 1\n",
    "            return count\n",
    "        def dfs(x,y):\n",
    "            count = check(x,y)\n",
    "            if not count :\n",
    "                board[x][y] = 'B'\n",
    "                for m,n in ((x+1,y),(x-1,y),(x-1,y-1),(x+1,y-1),(x-1,y+1),(x+1,y+1),(x,y-1),(x,y+1)):\n",
    "                    if 0 <= m < len(board) and 0 <= n < len(board[0]) and board[m][n] == 'E':\n",
    "                        dfs(m,n)\n",
    "            else:\n",
    "                board[x][y] = str(count)\n",
    "        dfs(click[0],click[1])\n",
    "        return board\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < m and 0 <= j < n and not vis[i][j]:\n",
    "                vis[i][j] = True\n",
    "                if board[i][j] == 'M':\n",
    "                    board[i][j] = 'X'\n",
    "                    return \n",
    "                elif board[i][j] == 'E':\n",
    "                    cnt = 0\n",
    "                    for x, y in (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1):\n",
    "                        if 0 <= x < m and 0 <= y < n and board[x][y] == \"M\":\n",
    "                            cnt += 1\n",
    "                    if cnt:\n",
    "                        board[i][j] = str(cnt)\n",
    "                    else:\n",
    "                        board[i][j] = 'B'\n",
    "                        for x, y in (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1):\n",
    "                            dfs(x, y)\n",
    "        \n",
    "        dfs(click[0], click[1])\n",
    "        return board\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        r, c = click[0], click[1]\n",
    "\n",
    "        # find mine\n",
    "        if board[r][c] == 'M':\n",
    "            board[r][c] = 'X'\n",
    "            return board\n",
    "\n",
    "        # find empty block\n",
    "        if board[r][c] == 'E':\n",
    "            m, n = len(board), len(board[0])\n",
    "            self.dfs(r, c, board, m, n)\n",
    "            return board\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, r, c, board, m, n):\n",
    "        if not self.boarderCheck(r, c, board, m, n):\n",
    "            return\n",
    "        if board[r][c] != 'E':\n",
    "            return\n",
    "        moves = []\n",
    "        for i in [-1, 0, 1]:\n",
    "            for j in [-1, 0, 1]:\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                moves.append([r+i, c+j])\n",
    "        if board[r][c] == 'E':\n",
    "            nearMine = 0\n",
    "            for newr, newc in moves:\n",
    "                if self.boarderCheck(newr, newc, board, m, n) and board[newr][newc] == 'M':\n",
    "                    nearMine += 1 \n",
    "            if nearMine > 0:\n",
    "                board[r][c] = str(nearMine)\n",
    "            else:\n",
    "                board[r][c] = 'B'\n",
    "                for newr, newc in moves:\n",
    "                    self.dfs(newr, newc, board, m, n)\n",
    "\n",
    "    def boarderCheck(self, r, c, board, m, n):\n",
    "        if r < 0 or r >= m or c < 0 or c >= n:\n",
    "            return False\n",
    "        return True\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        cnt_bomb = collections.defaultdict(int)\n",
    "        dirs = [0, 1, 0, -1, 0]\n",
    "        dirs8 = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] != \"M\": continue\n",
    "                for k in range(8):\n",
    "                    ni, nj = i + dirs8[k][0], j + dirs8[k][1]\n",
    "                    if ni < 0 or nj < 0 or ni >= m or nj >= n or board[ni][nj] != \"E\": continue\n",
    "                    cnt_bomb[(ni, nj)] += 1 \n",
    "        #print(cnt_bomb)\n",
    "\n",
    "        def open_blocks(i, j):\n",
    "            if cnt_bomb[(i, j)] > 0:\n",
    "                board[i][j] = str(cnt_bomb[(i, j)])\n",
    "                return\n",
    "            else:\n",
    "                board[i][j] = \"B\"\n",
    "            for k in range(8):\n",
    "                ni, nj = i + dirs8[k][0], j + dirs8[k][1]\n",
    "                if ni < 0 or nj < 0 or ni >= m or nj >= n or board[ni][nj] != \"E\": continue\n",
    "                open_blocks(ni, nj)\n",
    "            return\n",
    "\n",
    "        i, j = click\n",
    "        if board[i][j] == \"M\":\n",
    "            board[i][j] = \"X\"\n",
    "            return board\n",
    "        else:\n",
    "            open_blocks(i, j) \n",
    "\n",
    "        return board\n",
    "[[\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\"],\n",
    "[\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"M\"],\n",
    "[\"E\",\"E\",\"M\",\"E\",\"E\",\"E\",\"E\",\"E\"],\n",
    "[\"M\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\"],\n",
    "[\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\"],\n",
    "[\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\"],\n",
    "[\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\",\"E\"],\n",
    "[\"E\",\"E\",\"M\",\"M\",\"E\",\"E\",\"E\",\"E\"]]\n",
    "\n",
    "\n",
    "[[\"B\",\"B\",\"B\",\"B\",\"B\",\"B\",\"1\",\"E\"],\n",
    "[\"B\",\"1\",\"1\",\"1\",\"B\",\"B\",\"1\",\"M\"],\n",
    "[\"1\",\"E\",\"M\",\"1\",\"B\",\"B\",\"1\",\"1\"],\n",
    "[\"M\",\"E\",\"1\",\"1\",\"B\",\"B\",\"B\",\"B\"],\n",
    "[\"1\",\"1\",\"B\",\"B\",\"B\",\"B\",\"B\",\"B\"],\n",
    "[\"B\",\"B\",\"B\",\"B\",\"B\",\"B\",\"B\",\"B\"],\n",
    "[\"B\",\"1\",\"2\",\"2\",\"1\",\"B\",\"B\",\"B\"],\n",
    "[\"B\",\"1\",\"M\",\"M\",\"1\",\"B\",\"B\",\"B\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        # m = len(board)\n",
    "        # n = len(board[0])\n",
    "\n",
    "\n",
    "        # def get_negihbours(x,y):\n",
    "        #     for nx,ny in [(x - 1,y),(x + 1,y),(x,y - 1),(x,y + 1)]:\n",
    "        #         if 0 <= nx < m and 0 <= ny < n:\n",
    "        #             yield nx,ny\n",
    "\n",
    "        # def dfs(x,y):\n",
    "        #     nonlocal board\n",
    "        #     if board[x][y] == 'M':\n",
    "        #         board[x][y] = 'X'\n",
    "        #         return \n",
    "        #     if board[x][y] == \"E\":\n",
    "        #         board[x][y] == 'B'\n",
    "        #     for nx,ny in get_negihbours(x,y):\n",
    "        #         if board[nx][ny] == 'M':\n",
    "        #             if board[x][y] == 'B': \n",
    "        #                 board[x][y] = 1\n",
    "        #             else:\n",
    "        #                 board[x][y] = 1\n",
    "        #         if (nx,ny) not in vis:\n",
    "        #             vis.add((nx,ny))\n",
    "        #             dfs(nx,ny)\n",
    "        # vis = set(click)\n",
    "        # dfs(click[0],click[1])\n",
    "        # return board\n",
    "        ###########错误点：未考虑全部八个方向###############\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "\n",
    "        def get_negihbours(x,y):\n",
    "            for nx,ny in [(x - 1,y),(x + 1,y),(x,y - 1),(x,y + 1),(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    yield nx,ny\n",
    "\n",
    "        def dfs(x,y):\n",
    "            if board[x][y] == 'M':\n",
    "                board[x][y] = 'X'\n",
    "                return \n",
    "            nub_of_minue = 0\n",
    "            # 重点在这里，遍历8个角度，寻找雷的数量\n",
    "            for nx,ny in get_negihbours(x,y):\n",
    "                if board[nx][ny] == 'M':\n",
    "                    nub_of_minue += 1\n",
    "            if nub_of_minue:\n",
    "                board[x][y] = str(nub_of_minue)\n",
    "            else:\n",
    "                # 没有雷的情况下，就是一个白板\n",
    "                board[x][y] = 'B'\n",
    "                for nx,ny in get_negihbours(x,y):\n",
    "                    # 在为探索的地方，进入dfs\n",
    "                    if board[nx][ny] == 'E':\n",
    "                        dfs(nx,ny)\n",
    "        vis = set(click)#不需要vis，因为遍历过的点都改变了值，所以不会重复遍历了\n",
    "        dfs(click[0],click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        self.board=board\n",
    "        self.move=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]\n",
    "        if click[0]>=len(board)or click[1]>=len(board[0])or click[0]<0 or click[1]<0:\n",
    "            return \n",
    "        if board[click[0]][click[1]]==\"M\":\n",
    "            board[click[0]][click[1]]=\"X\"\n",
    "            return board\n",
    "        if board[click[0]][click[1]]!=\"E\":\n",
    "            return \n",
    "        else:\n",
    "           board[click[0]][click[1]]=self.count(click[0],click[1])\n",
    "           if board[click[0]][click[1]]==\"B\":\n",
    "               i,j=click[0],click[1]\n",
    "               for mo in self.move:\n",
    "                   self.updateBoard(board,click=[i+mo[0],j+mo[1]])    \n",
    "        return board\n",
    "    #统计周围炸弹个数\n",
    "    def countif(self,i,j):\n",
    "        if i>=len(self.board)or j>=len(self.board[0])or i<0 or j<0:\n",
    "            return 0\n",
    "        else:\n",
    "            if self.board[i][j]==\"M\"or self.board[i][j]==\"X\":\n",
    "                return 1\n",
    "            return 0\n",
    "    def count(self,i,j): \n",
    "        res=str(self.countif(i-1,j-1)+self.countif(i-1,j)+self.countif(i-1,j+1)+self.countif(i,j-1)+self.countif(i,j+1)+self.countif(i+1,j-1)+self.countif(i+1,j)+self.countif(i+1,j+1) )\n",
    "        if res==\"0\":\n",
    "            return \"B\"\n",
    "        else:\n",
    "            return res\n",
    "    #递归\n",
    "    def nextlv(self,i,j):\n",
    "        if i>=len(self.board)or j>=len(self.board[0])or i<0 or j<0:\n",
    "            return \n",
    "        if self.board[i][j]==\"E\":\n",
    "            self.board[i][j]=self.count(i,j)\n",
    "            if self.board[i][j]==\"B\":\n",
    "               for mo in self. move:\n",
    "                   self.nextlv(i+mo[0],j+mo[1])   \n",
    "        return\n",
    "        \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < m and 0 <= j < n and board[i][j] == 'E':\n",
    "                board[i][j] = str(sum(map(lambda i, j: 1 if 0 <= i < m and 0 <= j < n and board[i][j] == 'M' else 0, (i-1,i+1,i,i,i-1,i+1,i-1,i+1), (j,j,j+1,j-1,j-1,j-1,j+1,j+1))))\n",
    "                if board[i][j] == '0':\n",
    "                    board[i][j] = 'B'\n",
    "                    for x, y in (i-1,j),(i+1,j),(i,j+1),(i,j-1),(i-1,j-1),(i+1,j-1),(i-1,j+1),(i+1,j+1):\n",
    "                        dfs(x, y)\n",
    "        if board[click[0]][click[1]] == 'M':\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "        else:\n",
    "            dfs(click[0], click[1])\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        clicked = board[click[0]][click[1]]\n",
    "        if clicked == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        def neighb(x, y):\n",
    "            ans = []\n",
    "            y_ = [1, 1, 0, -1, -1, -1, 0, 1]\n",
    "            x_ = [0, -1, -1, -1, 0, 1, 1, 1]\n",
    "            for i in range(8):\n",
    "                x_new = x + x_[i]\n",
    "                y_new = y + y_[i]\n",
    "                if x_new >= 0 and x_new < m and y_new >= 0 and y_new < n:\n",
    "                    ans.append([x + x_[i], y + y_[i]])\n",
    "            return ans\n",
    "\n",
    "\n",
    "        def dfs(x, y):\n",
    "            n = 0\n",
    "            for i in neighb(x, y):\n",
    "                if board[i[0]][i[1]] == \"M\":\n",
    "                    n += 1\n",
    "            if n > 0:\n",
    "                board[x][y] = str(n)\n",
    "                return\n",
    "            board[x][y] = \"B\"\n",
    "            for i in neighb(x, y):\n",
    "                if board[i[0]][i[1]] == \"E\":\n",
    "                    dfs(i[0], i[1])\n",
    "        \n",
    "        dfs(click[0], click[1])\n",
    "\n",
    "        return board\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
